On the maximum cardinality search lower bound for treewidth

DOI10.1016/j.dam.2007.02.004zbMath1119.05101OpenAlexW2159851316WikidataQ59567777 ScholiaQ59567777MaRDI QIDQ997060

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

Publication date: 19 July 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.02.004

zbMATH Keywords

planar graphstreewidthlower boundsgraph algorithmsmaximum cardinality search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Constructing Brambles, Treewidth computations. II. Lower bounds, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Uses Software

• Treewidthlib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Girth and treewidth
• Safe separators for treewidth
• Safe reduction rules for weighted treewidth
• A spectral lower bound for the treewidth of a graph and its consequences
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Graph minors. II. Algorithmic aspects of tree-width
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search
• Solving partial constraint satisfaction problems with tree decomposition
• Contraction and Treewidth Lower Bounds
• Algorithms – ESA 2005
• Heuristic and metaheuristic methods for computing graph treewidth
• Experimental and Efficient Algorithms
• Experimental and Efficient Algorithms
• A sufficiently fast algorithm for finding close to optimal clique trees