On the maximum cardinality search lower bound for treewidth
DOI10.1016/J.DAM.2007.02.004zbMATH Open1119.05101DBLPjournals/dam/BodlaenderK07OpenAlexW2159851316WikidataQ59567777 ScholiaQ59567777MaRDI QIDQ997060FDOQ997060
Authors: 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
Recommendations
- Graph-Theoretic Concepts in Computer Science
- A New Lower Bound for Tree-Width Using Maximum Cardinality Search
- A lower bound for treewidth and its consequences
- Graph searching and a min-max theorem for tree-width
- Treewidth computations. II. Lower bounds
- On treewidth approximations
- Upper bounds for maximally greedy binary search trees
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- On Exact Algorithms for Treewidth
- Lower bounds on the size of general branch-and-bound trees
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- A sufficiently fast algorithm for finding close to optimal clique trees
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A spectral lower bound for the treewidth of a graph and its consequences
- Treewidth: computational experiments
- Girth and treewidth
- Contraction and Treewidth Lower Bounds
- Safe separators for treewidth
- Experimental and Efficient Algorithms
- Title not available (Why is that?)
- A New Lower Bound for Tree-Width Using Maximum Cardinality Search
- Title not available (Why is that?)
- Heuristic and metaheuristic methods for computing graph treewidth
- Solving partial constraint satisfaction problems with tree decomposition
- Safe reduction rules for weighted treewidth
- Algorithms – ESA 2005
- Experimental and Efficient Algorithms
Cited In (7)
- Treewidth computations. II. Lower bounds
- Graph searching and a min-max theorem for tree-width
- How to survive while visiting a graph
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Constructing Brambles
- Obtaining Optimalk-Cardinality Trees Fast
- Graph-Theoretic Concepts in Computer Science
Uses Software
This page was built for publication: On the maximum cardinality search lower bound for treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q997060)
