Treewidth lower bounds with brambles

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

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

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 algorithmLower boundPlanar graphGrid minorBrambleTreewidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Constructing Brambles, Treewidth of Cartesian Products of Highly Connected Graphs, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Fission: Practical algorithms for computing minimum balanced node separators, Tree-width of hypergraphs and surface duality, A note on planar graphs with large width parameters and small grid-minors, Parameters Tied to Treewidth, Implicit branching and parameterized partial cover problems, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, A branch-and-price-and-cut method for computing an optimal bramble, Fast minor testing in planar graphs, Treewidth computations. II. Lower bounds, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Lower bounds for treewidth of product graphs, Encoding Treewidth into SAT, On planar graphs with large tree-width and small grid minors, Brambles and independent packings in chordal graphs

Uses Software

• Treewidthlib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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