On polynomial time decidability of induced-minor-closed classes
Matoušek, Jiří ; Nešetřil, Jaroslav ; Thomas, Robin D.
Commentationes Mathematicae Universitatis Carolinae, Tome 029 (1988), p. 703-710 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1988-01-01
Classification:  05C99,  68E10,  68Q20,  68Q25,  68R10 
@article{106687,
     author = {Ji\v r\'\i\ Matou\v sek and Jaroslav Ne\v set\v ril and Robin D. Thomas},
     title = {On polynomial time decidability of induced-minor-closed classes},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {029},
     year = {1988},
     pages = {703-710},
     zbl = {0668.68048},
     mrnumber = {982789},
     language = {en},
     url = {http://dml.mathdoc.fr/item/106687}
}

Matoušek, Jiří; Nešetřil, Jaroslav; Thomas, Robin D. On polynomial time decidability of induced-minor-closed classes. Commentationes Mathematicae Universitatis Carolinae, Tome 029 (1988) pp. 703-710. http://gdmltest.u-ga.fr/item/106687/

S. Arnborg A. Proskurowski Linear time algorithms for NP-hard problems on graphs embedded in k-trees, submitted.

S. Arnborg A. Proskurowski Characterization and recognition of partial 3-trees, SIAM 3. Alg. Disc. Math. Vol.7, No. 2 (1986), 305-314. (1986) | MR 0830649

M. Fellows M. Langston Nonconstructive tools for proving polynomial-time decidability, to appear in JACM. | MR 0963169

J. Kratochvíl J. Golian P. Kučera String graphs, Academia, Prague (1987), p. 105. (1987)

J. Matoušek R. Thomas Algorithms finding tree-decompositions of graphs, submitted.

J. Nešetřil R. Thomas A note on spatial Representation of Graphs, Comment. Math. Univ. Carolinae 26 (1985), 655-659. (1985) | MR 0831801

N. Robertson P. S. Seymour Graph Minors V. Excluding a planar graph, J. Combin. Theory, Ser. B 41 (1986), 92-114. (1986) | MR 0854606

N. Robertson P. D. Seymour Graph Minors X. Obstructions to treedecomposition, submitted.

N. Robertson P. D. Seymour Graph Minors XIII. The disjoint paths problem, submitted.

R. Thomas Graphs without $K_4$ and well-quasi-ordering, J. Combin. Theory, Ser. (B) 38 (1985), 240-247. (1985) | MR 0796601

K. Wagner Bemerkungen zu Hadwigers Vermutung, Math. Ann. 141 (1960), 433-451. (1960) | MR 0121309 | Zbl 0096.17904