On the complexity of computing treebreadth

DOI10.1007/978-3-319-44543-4_1MaRDI QIDQ2819486zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse

Publication date 29 September 2016

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

Full work available at URL https://hal.inria.fr/hal-01354996/file/DLN-IWOCA16.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the complexity of computing treebreadth
• On strong tree-breadth
• On the complexity of computing treelength
• On the Complexity of Computing Treelength
• A short note on the complexity of computing strong pathbreadth

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• An introduction to clique minimal separator decomposition
• Complexity of Finding Embeddings in a k-Tree
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Dually Chordal Graphs
• Feedback Vertex Sets on Tree Convex Bipartite Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Inapproximability of treewidth and related problems
• Line-distortion, bandwidth and path-length of a graph
• On the complexity of computing treebreadth
• On the complexity of computing treelength
• On the minimum eccentricity shortest path problem
• Spanners for bounded tree-length graphs
• To approximate treewidth, use treelength!
• Tree-decompositions with bags of small diameter
• Treewidth: Characterizations, Applications, and Computations

Cited in

(14)

• 3-colouring for dually chordal graphs and generalisations
• Treewidth and the Computational Complexity of MAP Approximations
• On the Complexity of Computing Treelength
• On strong tree-breadth
• On the complexity of computing treebreadth
• On the complexity of computing treebreadth
• Complexity Analysis of Generalized and Fractional Hypertree Decompositions
• Equivalence between pathbreadth and strong pathbreadth
• On the complexity of computing treelength
• On the computational complexity of the rooted subtree prune and regraft distance
• The complexity of bicriteria tree-depth
• Estimating the Size of Branch-and-Bound Trees
• Computing Tree-Depth Faster Than 2 n
• A short note on the complexity of computing strong pathbreadth

This page was built for publication: On the complexity of computing treebreadth

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