On exact algorithms for treewidth

DOI10.1145/2390176.2390188MaRDI QIDQ2933641zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos, 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 programmingexact algorithmsgraph algorithmsseparators\textsc{Treewidth}

Mathematics Subject Classification ID

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

Recommendations

• On Exact Algorithms for Treewidth
• On treewidth approximations
• Publication:4699283
• The algorithmic theory of treewidth
• Approximation algorithms for treewidth
• Automata, Languages and Programming
• Exact Algorithms for Treewidth and Minimum Fill-In
• A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
• Branching and Treewidth Based Exact Algorithms
• Treewidth: Characterizations, Applications, and Computations

Cited in

(33)

• Positive-instance driven dynamic programming for treewidth
• Exact algorithms for intervalizing coloured graphs
• An algorithmic metatheorem for directed treewidth
• On Exact Algorithms for Treewidth
• A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
• Treewidth computation and extremal combinatorics
• Positive-instance driven dynamic programming for treewidth
• Approximately counting locally-optimal structures
• Space-efficient vertex separators for treewidth
• Treewidth distance on phylogenetic trees
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Treewidth Computation and Extremal Combinatorics
• On the \(k\)-rainbow domination in graphs with bounded tree-width
• Computing treewidth on the GPU
• An extended depth-first search algorithm for optimal triangulation of Bayesian networks
• Treewidth: Structure and Algorithms
• Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation
• Tractability of most probable explanations in multidimensional Bayesian network classifiers
• An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
• Treewidth and the Computational Complexity of MAP Approximations
• An Experimental Study of the Treewidth of Real-World Graph Data
• Branching and Treewidth Based Exact Algorithms
• Treewidth and pathwidth parameterized by the vertex cover number
• Automata, Languages and Programming
• Experimental Analysis of Treewidth
• On treewidth approximations
• Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
• Improving TSP tours using dynamic programming over tree decompositions
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• Exact and heuristic computation of the scanwidth of directed acyclic graphs
• On the satisfiability of quantum circuits of small treewidth
• Approximately Counting Locally-Optimal Structures
• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933641)