On polynomial time decidability of induced-minor-closed classes

Jiří Matoušek; Jaroslav Nešetřil; Robin D. Thomas

Commentationes Mathematicae Universitatis Carolinae (1988)

  • Volume: 029, Issue: 4, page 703-710
  • ISSN: 0010-2628

How to cite

top

Matoušek, Jiří, Nešetřil, Jaroslav, and Thomas, Robin D.. "On polynomial time decidability of induced-minor-closed classes." Commentationes Mathematicae Universitatis Carolinae 029.4 (1988): 703-710. <http://eudml.org/doc/17683>.

@article{Matoušek1988,
author = {Matoušek, Jiří, Nešetřil, Jaroslav, Thomas, Robin D.},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {tree-width; branch-width; well-quasi-ordering; minor; induced-minor; series-parallel graphs},
language = {eng},
number = {4},
pages = {703-710},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On polynomial time decidability of induced-minor-closed classes},
url = {http://eudml.org/doc/17683},
volume = {029},
year = {1988},
}

TY - JOUR
AU - Matoušek, Jiří
AU - Nešetřil, Jaroslav
AU - Thomas, Robin D.
TI - On polynomial time decidability of induced-minor-closed classes
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1988
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 029
IS - 4
SP - 703
EP - 710
LA - eng
KW - tree-width; branch-width; well-quasi-ordering; minor; induced-minor; series-parallel graphs
UR - http://eudml.org/doc/17683
ER -

References

top
  1. S. ARNBORG A. PROSKUROWSKI, Linear time algorithms for NP-hard problems on graphs embedded in k-trees, submitted. 
  2. S. ARNBORG A. PROSKUROWSKI, Characterization and recognition of partial 3-trees, SIAM 3. Alg. Disc. Math. Vol.7, No. 2 (1986), 305-314. (1986) MR0830649
  3. M. FELLOWS M. LANGSTON, Nonconstructive tools for proving polynomial-time decidability, to appear in JACM. MR0963169
  4. J. KRATOCHVÍL J. GOLIAN P. KUČERA, String graphs, Academia, Prague (1987), p. 105. (1987) 
  5. J. MATOUŠEK R. THOMAS, Algorithms finding tree-decompositions of graphs, submitted. 
  6. J. NEŠETŘIL R. THOMAS, A note on spatial Representation of Graphs, Comment. Math. Univ. Carolinae 26 (1985), 655-659. (1985) MR0831801
  7. N. ROBERTSON P. S. SEYMOUR, Graph Minors V. Excluding a planar graph, J. Combin. Theory, Ser. B 41 (1986), 92-114. (1986) MR0854606
  8. N. ROBERTSON P. D. SEYMOUR, Graph Minors X. Obstructions to treedecomposition, submitted. 
  9. N. ROBERTSON P. D. SEYMOUR, Graph Minors XIII. The disjoint paths problem, submitted. 
  10. R. THOMAS, Graphs without K 4 and well-quasi-ordering, J. Combin. Theory, Ser. (B) 38 (1985), 240-247. (1985) MR0796601
  11. K. WAGNER, Bemerkungen zu Hadwigers Vermutung, Math. Ann. 141 (1960), 433-451. (1960) Zbl0096.17904MR0121309

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.