On the maximum cardinality search lower bound for treewidth

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

zbMATH Keywords

planar graphs; treewidth; lower bounds; graph algorithms; maximum cardinality search

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Uses Software

• Treewidthlib