Graph minors. II. Algorithmic aspects of tree-width |
| |
| Institution: | 1. School of Informatics, University of Edinburgh, United Kingdom;2. Blocher Consulting, Champaign, IL, United States of America;1. School of Computer Science and Electrical Engineering, University of Ottawa, Ottawa, Canada;2. School of Computer Science, Carleton University, Ottawa, Canada;3. School of Mathematical Sciences, Monash University, Melbourne, Australia;1. Nagoya University, Nagoya, Japan;2. Seikei University, Musashino, Tokyo, Japan;3. Hokkaido University, Sapporo, Japan |
| |
| Abstract: | We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width ≤ w, for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
