On the Complexity of Computing Treebreadth
DOI10.1007/978-3-319-44543-4_1zbMath1478.68101OpenAlexW2547414465MaRDI QIDQ2819486
Sylvain Legay, Guillaume Ducoffe, 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
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
Cites Work
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- On the complexity of computing treelength
- An introduction to clique minimal separator decomposition
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- On the Complexity of Computing Treebreadth
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Line-Distortion, Bandwidth and Path-Length of a Graph
- On the Minimum Eccentricity Shortest Path Problem
- Treewidth: Characterizations, Applications, and Computations
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Dually Chordal Graphs
- Inapproximability of Treewidth and Related Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- To Approximate Treewidth, Use Treelength!
This page was built for publication: On the Complexity of Computing Treebreadth
