On computing graph minor obstruction sets

DOI10.1016/S0304-3975(97)00300-9zbMath0952.68116MaRDI QIDQ1575945

Michael R. Fellows, Michael A. Langston, Michael J. Dinneen, Kevin Cattell, Rodney G. Downey

Publication date: 23 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

obstruction width.second-order congruence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Graph theory (05C99)

Related Items (14)

A polynomial excluded-minor approximation of treedepth ⋮ Collaborating with Hans: Some Remaining Wonderments ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Combing a Linkage in an Annulus ⋮ Confronting intractability via parameters ⋮ Properties of vertex cover obstructions ⋮ Minor obstructions for apex-pseudoforests ⋮ FPT is characterized by useful obstruction sets ⋮ Minor-obstructions for apex sub-unicyclic graphs ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

Cites Work

• A simple linear-time algorithm for finding path-decompositions of small width
• Graph minors. XX: Wagner's conjecture
• Graph minors. I. Excluding a forest
• Quickly excluding a forest
• Obstruction set isolation for the gate matrix layout problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Nonconstructive tools for proving polynomial-time decidability
• Bounding the Size of Planar Intertwines
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• Obstructions to within a few vertices or edges of acyclic
• Two strikes against perfect phylogeny
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On computing graph minor obstruction sets