Treewidth lower bounds with brambles

DOI10.1007/s00453-007-9056-zzbMath1138.68065WikidataQ59567755 ScholiaQ59567755MaRDI QIDQ926284

Hans L. Bodlaender, Arie M. C. A. Koster, Alexander Grigoriev

Publication date: 27 May 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9056-z

zbMATH Keywords

Approximation algorithm; Lower bound; Planar graph; Grid minor; Bramble; Treewidth

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Treewidth computations. II. Lower bounds, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Brambles and independent packings in chordal graphs, Constructing Brambles, Encoding Treewidth into SAT

Uses Software

• Treewidthlib

Cites Work

• Safe separators for treewidth
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Highly connected sets and the excluded grid theorem
• Graph searching and a min-max theorem for tree-width
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• E ₁₁ and M theory
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Tour Merging via Branch-Decomposition
• Planar Branch Decompositions I: The Ratcatcher
• Planar Branch Decompositions II: The Cycle Method
• The Structure and Number of Obstructions to Treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Efficient Planarity Testing
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search
• Contraction and Treewidth Lower Bounds
• Algorithms – ESA 2004
• Automata, Languages and Programming
• Heuristic and metaheuristic methods for computing graph treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Experimental and Efficient Algorithms
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item