On exact algorithms for treewidth
DOI10.1145/2390176.2390188zbMATH Open1301.05328DBLPjournals/talg/BodlaenderFKKT12OpenAlexW1969259020WikidataQ59567551 ScholiaQ59567551MaRDI QIDQ2933641FDOQ2933641
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
Recommendations
- On Exact Algorithms for Treewidth
- On treewidth approximations
- scientific article; zbMATH DE number 1361465
- 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
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)
Cited In (28)
- Exact algorithms for intervalizing coloured graphs
- On the k-rainbow domination in graphs with bounded tree-width
- An algorithmic metatheorem for directed treewidth
- On Exact Algorithms for Treewidth
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- Positive-instance driven dynamic programming for treewidth
- Approximately counting locally-optimal structures
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
- Treewidth distance on phylogenetic trees
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Treewidth Computation and Extremal Combinatorics
- Computing treewidth on the GPU
- Positive-Instance Driven Dynamic Programming for Treewidth.
- Treewidth: Structure and Algorithms
- An extended depth-first search algorithm for optimal triangulation of Bayesian networks
- 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
- Automata, Languages and Programming
- Treewidth and pathwidth parameterized by the vertex cover number
- Experimental Analysis of Treewidth
- On treewidth approximations
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- 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)
