Geodesic
On polynomial time decidability of induced-minor-closed classes
Commentationes Mathematicae Universitatis Carolinae, Tome 29 (1988) no. 4, pp. 703-710 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 05C99, 68E10, 68Q20, 68Q25, 68R10 
@article{CMUC_1988_29_4_a9,
     author = {Matou\v{s}ek, Ji\v{r}{\'\i} and Ne\v{s}et\v{r}il, Jaroslav and Thomas, Robin},
     title = {On polynomial time decidability of induced-minor-closed classes},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {703--710},
     year = {1988},
     volume = {29},
     number = {4},
     mrnumber = {982789},
     zbl = {0668.68048},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1988_29_4_a9/}
}
TY  - JOUR
AU  - Matoušek, Jiří
AU  - Nešetřil, Jaroslav
AU  - Thomas, Robin
TI  - On polynomial time decidability of induced-minor-closed classes
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1988
SP  - 703
EP  - 710
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMUC_1988_29_4_a9/
LA  - en
ID  - CMUC_1988_29_4_a9
ER  - 
%0 Journal Article
%A Matoušek, Jiří
%A Nešetřil, Jaroslav
%A Thomas, Robin
%T On polynomial time decidability of induced-minor-closed classes
%J Commentationes Mathematicae Universitatis Carolinae
%D 1988
%P 703-710
%V 29
%N 4
%U http://geodesic.mathdoc.fr/item/CMUC_1988_29_4_a9/
%G en
%F CMUC_1988_29_4_a9
Matoušek, Jiří; Nešetřil, Jaroslav; Thomas, Robin. On polynomial time decidability of induced-minor-closed classes. Commentationes Mathematicae Universitatis Carolinae, Tome 29 (1988) no. 4, pp. 703-710. http://geodesic.mathdoc.fr/item/CMUC_1988_29_4_a9/

[AP] S. ARNBORG A. PROSKUROWSKI: Linear time algorithms for NP-hard problems on graphs embedded in k-trees. submitted.

[AP1] S. ARNBORG A. PROSKUROWSKI: Characterization and recognition of partial 3-trees. SIAM 3. Alg. Disc. Math. Vol.7, No. 2 (1986), 305-314. | MR

[FL] M. FELLOWS M. LANGSTON: Nonconstructive tools for proving polynomial-time decidability. to appear in JACM. | MR

[KGK] J. KRATOCHVÍL J. GOLIAN P. KUČERA: String graphs. Academia, Prague (1987), p. 105.

[MT] J. MATOUŠEK R. THOMAS: Algorithms finding tree-decompositions of graphs. submitted.

[NT] J. NEŠETŘIL R. THOMAS: A note on spatial Representation of Graphs. Comment. Math. Univ. Carolinae 26 (1985), 655-659. | MR

[RS1] N. ROBERTSON P. S. SEYMOUR: Graph Minors V. Excluding a planar graph. J. Combin. Theory, Ser. B 41 (1986), 92-114. | MR

[RS2] N. ROBERTSON P. D. SEYMOUR: Graph Minors X. Obstructions to treedecomposition. submitted.

[RS3] N. ROBERTSON P. D. SEYMOUR: Graph Minors XIII. The disjoint paths problem. submitted.

[T] R. THOMAS: Graphs without $K_4$ and well-quasi-ordering. J. Combin. Theory, Ser. (B) 38 (1985), 240-247. | MR

[W] K. WAGNER: Bemerkungen zu Hadwigers Vermutung. Math. Ann. 141 (1960), 433-451. | MR | Zbl