On the maximum cardinality search lower bound for treewidth
From MaRDI portal
Publication:997060
DOI10.1016/j.dam.2007.02.004zbMath1119.05101MaRDI QIDQ997060
Hans L. Bodlaender, Arie M. C. A. Koster
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Uses Software
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