On treewidth approximations

MaRDI QIDQ2816043zbMATH OpenFDO

Authors Vincent Bouchitté, Dieter Kratsch, Haiko Müller, Ioan Todinca

Publication date 1 July 2016

Full work available at URL http://www.sciencedirect.com/science/article/pii/S1571065305800915?np=y

zbMATH Keywords

graphs of bounded asteroidal number

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Approximation algorithms for treewidth
• On treewidth approximations.
• On Exact Algorithms for Treewidth
• Treewidth and the Computational Complexity of MAP Approximations
• On exact algorithms for treewidth
• scientific article; zbMATH DE number 1361465
• Treewidth: Characterizations, Applications, and Computations
• The algorithmic theory of treewidth
• On Tamaki's Algorithm to Compute Treewidths.
• Inapproximability of treewidth and related problems

Cited in

(27)

• On approximating tree spanners that are breadth first search trees
• Approximating the treewidth of AT-free graphs.
• Special issue: Treewidth
• Estimating the Size of Branch-and-Bound Trees
• A \(c^k n\) 5-approximation algorithm for treewidth
• On the maximum cardinality search lower bound for treewidth
• Graphs with at most two moplexes
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• On the approximability of two tree drawing conventions
• scientific article; zbMATH DE number 219228 (Why is no real title available?)
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• On the complexity of computing treelength
• Treewidth: Structure and Algorithms
• Approximate Tree Matching in the Presence of Variable Length Don′t Cares
• scientific article; zbMATH DE number 1445378 (Why is no real title available?)
• Treewidth and the Computational Complexity of MAP Approximations
• On exact algorithms for treewidth
• Fast Counting with Bounded Treewidth
• scientific article; zbMATH DE number 7310078 (Why is no real title available?)
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• On treewidth approximations.
• Boxicity and treewidth
• Practical approximation algorithms for zero- and bounded-skew trees
• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• Inapproximability of treewidth, one-shot pebbling, and related layout problems
• Tree-decompositions with bags of small diameter

This page was built for publication: On treewidth approximations

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