On Exact Algorithms for Treewidth

DOI10.1007/11841036_60zbMath1131.68481OpenAlexW2104739701MaRDI QIDQ5449570

Dimitrios M. Thilikos, Arie M. C. A. Koster, Fedor V. Fomin, Dieter Kratsch, Hans L. Bodlaender

Publication date: 11 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/22183

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Differential geometric treewidth estimation in adiabatic quantum computation, Treewidth computation and extremal combinatorics, On integer linear programs for treewidth based on perfect elimination orderings, A combinatorial optimization algorithm for solving the branchwidth problem, Digraph measures: Kelly decompositions, games, and orderings, Solving Graph Problems via Potential Maximal Cliques, A note on exact algorithms for vertex ordering problems on graphs, Treewidth computations. I: Upper bounds, Minimum dominating set of queens: a trivial programming exercise?, Treewidth computations. II. Lower bounds, Learning tractable Bayesian networks in the space of elimination orders, Bandwidth of bipartite permutation graphs in polynomial time, Unnamed Item, Unnamed Item, On sparsification for computing treewidth, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth