%0 Journal Article %1 robertson1986graph %A Robertson, Neil %A Seymour, P. D. %D 1986 %J Journal of Algorithms %K complexity decomposition graph theory tree tree-width width %N 3 %P 309 - 322 %R 10.1016/0196-6774(86)90023-4 %T Graph minors. II. Algorithmic aspects of tree-width %U http://www.sciencedirect.com/science/article/B6WH3-4D7JNPT-98/2/5cff5f0f3d0cbbb7304ab079398cbf48 %V 7 %X 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.

@article{robertson1986graph, 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.}, added-at = {2010-10-06T11:31:32.000+0200}, author = {Robertson, Neil and Seymour, P. D.}, biburl = {https://www.bibsonomy.org/bibtex/2b51c80454f9d6c24148b17b6cc294123/folke}, description = {ScienceDirect - Journal of Algorithms : Graph minors. II. Algorithmic aspects of tree-width}, doi = {10.1016/0196-6774(86)90023-4}, interhash = {24d219e67df5cb2a6f5f48d71c669bb7}, intrahash = {b51c80454f9d6c24148b17b6cc294123}, issn = {0196-6774}, journal = {Journal of Algorithms}, keywords = {complexity decomposition graph theory tree tree-width width}, number = 3, pages = {309 - 322}, timestamp = {2010-10-06T11:33:12.000+0200}, title = {Graph minors. II. Algorithmic aspects of tree-width}, url = {http://www.sciencedirect.com/science/article/B6WH3-4D7JNPT-98/2/5cff5f0f3d0cbbb7304ab079398cbf48}, volume = 7, year = 1986 }