A New Lower Bound for Tree-Width Using Maximum Cardinality Search

DOI10.1137/S0895480101397773zbMath1041.68071MaRDI QIDQ4443091

Brian Lucena

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

triangulationlower boundtree-widthmaximum cardinality search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graphical methods in statistics (62A09)

Related Items (6)

Achievable sets, brambles, and sparse treewidth obstructions ⋮ Treewidth lower bounds with brambles ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Treewidth computations. II. Lower bounds ⋮ On the maximum cardinality search lower bound for treewidth

This page was built for publication: A New Lower Bound for Tree-Width Using Maximum Cardinality Search