Contraction and Treewidth Lower Bounds
From MaRDI portal
Publication:5301380
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
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