Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications

DOI10.1007/s00453-011-9545-yzbMath1264.05131OpenAlexW2148842617WikidataQ57359664 ScholiaQ57359664MaRDI QIDQ1759678

Danny Hermelin, Michael R. Fellows, Frances A. Rosamond

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9545-y

zbMATH Keywords

intersection graphtreewidthtree decompositionexact algorithmparameterized complexitystring graphwell quasi orderbounded circumferencebounded feedback vertex setbounded vertex covermeta algorithm

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83)

Related Items

Structural parameterizations for boxicity ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Well-quasi-ordering \(H\)-contraction-free graphs ⋮ Induced minors and well-quasi-ordering ⋮ Recent Progress on Well-Quasi-ordering Graphs ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of some colorful problems parameterized by treewidth
• Graph minors. XX: Wagner's conjecture
• Graph-modeled data clustering: Exact algorithms for clique generation
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graphs without \(K_ 4\) and well-quasi-ordering
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Min Cut is NP-complete for edge weighted trees
• String graphs. II: Recognizing string graphs is NP-hard
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• String graphs. I: The number of critical nonstring graphs is infinite
• Letter graphs and well-quasi-order by induced subgraphs
• Unit disk graph recognition is NP-hard
• Recognizing string graphs is decidable
• Decidability of string graphs
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• Faster Parameterized Algorithms for Minor Containment
• Algorithmic Meta-theorems for Restrictions of Treewidth
• Graph Layout Problems Parameterized by Vertex Cover
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• The Complexity of the Partial Order Dimension Problem
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Nonconstructive tools for proving polynomial-time decidability
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Subgraphs and well‐quasi‐ordering
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Bidimensionality and Geometric Graphs
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Induced subgraphs and well‐quasi‐ordering
• Ordering by Divisibility in Abstract Algebras
• Recognizing string graphs in NP
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s