Name
Title | ||
|---|---|---|
Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications |
Abstract | ||
|---|---|---|
We show that three subclasses of bounded treewidth graphs are well quasi ordered by refinements of the minor order. Specifically, we prove that graphs with bounded vertex cover are well quasi ordered by the induced subgraph order, graphs with bounded feedback vertex set are well quasi ordered by the topological-minor order, and graphs with bounded circumference are well quasi ordered by the induced minor order. Our results give algorithms for recognizing any graph family in these classes which is closed under the corresponding minor order refinement. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00453-011-9545-y | Algorithmica |
Keywords | Field | DocType |
Well quasi order,Treewidth,Tree decomposition,Bounded vertex cover graphs,Bounded feedback vertex set graphs,Bounded circumference graphs,Parameterized complexity,Exact algorithms,Meta-algorithms,Geometric graph recognition,String graphs | Discrete mathematics,Indifference graph,Combinatorics,Tree-depth,Partial k-tree,Chordal graph,Clique-sum,Treewidth,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
64 | 1 | 0178-4617 |
Citations | PageRank | References |
9 | 0.54 | 33 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Danny Hermelin | 2 | 790 | 48.62 |
| Frances A. Rosamond | 3 | 21 | 2.83 |