Algorithm Aspect of Graph Minor Theory
スポンサーリンク
概要
- 論文の詳細を見る
We shall survey recent progress on algorithm aspect of graph minor theory. One of the main results on Graph Minor Project by Robertson and Seymour is the following. Given a graph G and p pairs of vertices of G for fixed p, there is a polynomial time (actually O(n^3) algorithm to decide if there are p mutually disjoint paths of G linking the pair. If p is part of the input of the problem, then this is one of Karp's NP-complete problems, and it remains NP-complete even for planar graphs. We shall first sketch the algorithm, and explain why the correctness needs ? 500 pages to prove. Then we shall focus on applications of this result. Topics include tree-width for planar graphs, 2-path problem (2-linked graph), the odd disjoint cycles, the parity paths problems, Kuratowski's theorem for general surface, nearly-/c-bipartite graph problem and algorithm aspect of Hadwiger's conjecture.
- 一般社団法人情報処理学会の論文
- 2004-10-14
著者
-
Kawarabayashi Ken-ichi
Graduate School Of Information Sciences (gsis) Tohoku University
-
Kawarabayashi Ken-ichi
Graduate School Of Information Sciences(gsis):tohoku University
関連論文
- Algorithm Aspect of Graph Minor Theory
- Algorithm Aspect of Graph Minor Theory
- On Properties of a Set of Global Roundings Associated with Clique Connection of Graphs