On the complexity of computing treebreadth
DOI10.1007/978-3-319-44543-4_1zbMATH Open1478.68101OpenAlexW2547414465MaRDI QIDQ2819486FDOQ2819486
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
Recommendations
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)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Complexity of Finding Embeddings in a k-Tree
- Spanners for bounded tree-length graphs
- Graph minors. II. Algorithmic aspects of tree-width
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Dually Chordal Graphs
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- On the complexity of computing treelength
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- To approximate treewidth, use treelength!
- Treewidth: Characterizations, Applications, and Computations
- An introduction to clique minimal separator decomposition
- Tree-decompositions with bags of small diameter
- Line-distortion, bandwidth and path-length of a graph
- On the minimum eccentricity shortest path problem
- Inapproximability of treewidth and related problems
- On the complexity of computing treebreadth
Cited In (14)
- On the computational complexity of the rooted subtree prune and regraft distance
- 3-colouring for dually chordal graphs and generalisations
- Estimating the Size of Branch-and-Bound Trees
- On the Complexity of Computing Treelength
- On the complexity of computing treebreadth
- On the complexity of computing treebreadth
- On strong tree-breadth
- On the complexity of computing treelength
- Treewidth and the Computational Complexity of MAP Approximations
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- Equivalence between pathbreadth and strong pathbreadth
- A short note on the complexity of computing strong pathbreadth
- Computing Tree-Depth Faster Than 2 n
- The complexity of bicriteria tree-depth
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)
