On exact algorithms for treewidth

DOI10.1145/2390176.2390188zbMath1301.05328OpenAlexW1969259020WikidataQ59567551 ScholiaQ59567551MaRDI QIDQ2933641

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

Publication date: 5 December 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2390176.2390188

zbMATH Keywords

dynamic programminggraph algorithmsexact algorithmsseparators\textsc{Treewidth}

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

Experimental Analysis of Treewidth ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ An extended depth-first search algorithm for optimal triangulation of Bayesian networks ⋮ Treewidth distance on phylogenetic trees ⋮ On the k-rainbow domination in graphs with bounded tree-width ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ Positive-instance driven dynamic programming for treewidth ⋮ Tractability of most probable explanations in multidimensional Bayesian network classifiers ⋮ \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions ⋮ An exact exponential branch-and-merge algorithm for the single machine total tardiness problem ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ Positive-Instance Driven Dynamic Programming for Treewidth. ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ Computing treewidth on the GPU ⋮ Exact algorithms for intervalizing coloured graphs

This page was built for publication: On exact algorithms for treewidth