On the maximum cardinality search lower bound for treewidth

DOI10.1016/J.DAM.2007.02.004MaRDI QIDQ997060zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

treewidthlower boundsgraph algorithmsplanar graphsmaximum cardinality search

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1953092 (Why is no real title available?)
• scientific article; zbMATH DE number 1982177 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search
• A spectral lower bound for the treewidth of a graph and its consequences
• A sufficiently fast algorithm for finding close to optimal clique trees
• Algorithms – ESA 2005
• Contraction and Treewidth Lower Bounds
• Experimental and Efficient Algorithms
• Experimental and Efficient Algorithms
• Girth and treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• Heuristic and metaheuristic methods for computing graph treewidth
• Safe reduction rules for weighted treewidth
• Safe separators for treewidth
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Solving partial constraint satisfaction problems with tree decomposition
• Treewidth: computational experiments

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

Describes a project that uses

Uses Software

• Treewidthlib

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)