| Title:
|
On polynomial time decidability of induced-minor-closed classes (English) |
| Author:
|
Matoušek, Jiří |
| Author:
|
Nešetřil, Jaroslav |
| Author:
|
Thomas, Robin |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
29 |
| Issue:
|
4 |
| Year:
|
1988 |
| Pages:
|
703-710 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C99 |
| MSC:
|
68E10 |
| MSC:
|
68Q20 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0668.68048 |
| idMR:
|
MR982789 |
| . |
| Date available:
|
2008-06-05T21:35:52Z |
| Last updated:
|
2012-04-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/106687 |
| . |
| Reference:
|
[AP] S. ARNBORG A. PROSKUROWSKI: Linear time algorithms for NP-hard problems on graphs embedded in k-trees.submitted. |
| Reference:
|
[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 0830649 |
| Reference:
|
[FL] M. FELLOWS M. LANGSTON: Nonconstructive tools for proving polynomial-time decidability.to appear in JACM. MR 0963169 |
| Reference:
|
[KGK] J. KRATOCHVÍL J. GOLIAN P. KUČERA: String graphs.Academia, Prague (1987), p. 105. |
| Reference:
|
[MT] J. MATOUŠEK R. THOMAS: Algorithms finding tree-decompositions of graphs.submitted. |
| Reference:
|
[NT] J. NEŠETŘIL R. THOMAS: A note on spatial Representation of Graphs.Comment. Math. Univ. Carolinae 26 (1985), 655-659. MR 0831801 |
| Reference:
|
[RS1] N. ROBERTSON P. S. SEYMOUR: Graph Minors V. Excluding a planar graph.J. Combin. Theory, Ser. B 41 (1986), 92-114. MR 0854606 |
| Reference:
|
[RS2] N. ROBERTSON P. D. SEYMOUR: Graph Minors X. Obstructions to treedecomposition.submitted. |
| Reference:
|
[RS3] N. ROBERTSON P. D. SEYMOUR: Graph Minors XIII. The disjoint paths problem.submitted. |
| Reference:
|
[T] R. THOMAS: Graphs without $K_4$ and well-quasi-ordering.J. Combin. Theory, Ser. (B) 38 (1985), 240-247. MR 0796601 |
| Reference:
|
[W] K. WAGNER: Bemerkungen zu Hadwigers Vermutung.Math. Ann. 141 (1960), 433-451. Zbl 0096.17904, MR 0121309 |
| . |
