Contraction and Treewidth Lower Bounds

DOI10.7155/jgaa.00117zbMath1161.68644OpenAlexW2103080151MaRDI QIDQ5301380

Arie M. C. A. Koster, Thomas Wolle, Hans L. Bodlaender

Publication date: 19 January 2009

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/55396

zbMATH Keywords

bipartite graphsedge contractioncontraction degeneracy

Mathematics Subject Classification ID

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

Related Items

Neighborhood contraction in graphs, Increasing the Minimum Degree of a Graph by Contractions, Constructing Brambles, Increasing the minimum degree of a graph by contractions, Fission: Practical algorithms for computing minimum balanced node separators, Positive-instance driven dynamic programming for treewidth, Edge degeneracy: algorithmic and structural results, A combinatorial optimization algorithm for solving the branchwidth problem, Treewidth lower bounds with brambles, Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization, A branch-and-price-and-cut method for computing an optimal bramble, Treewidth computations. I: Upper bounds, Treewidth computations. II. Lower bounds, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, On the maximum cardinality search lower bound for treewidth, Unnamed Item, Encoding Treewidth into SAT, Searching for a Visible, Lazy Fugitive, Positive-Instance Driven Dynamic Programming for Treewidth., Worst-case analysis of clique MIPs