On the complexity of computing treebreadth
From MaRDI portal
Publication:1987233
bipartite graphsgraph theoryNP-completenesspathbreadthpathlengthplanar graphsRobertson and Seymour's tree decompositiontreebreadth
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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Recommendations
Cites work
- 3-colouring for dually chordal graphs and generalisations
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A short note on the complexity of computing strong pathbreadth
- Algorithmic graph theory and perfect graphs
- Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- An introduction to clique minimal separator decomposition
- Better approximation algorithms for the graph diameter
- Characterizations and algorithmic applications of chordal graph embeddings
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Complexity of Finding Embeddings in a k-Tree
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Dually Chordal Graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of 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
- Listing all potential maximal cliques of a graph
- Metric Dimension of Bounded Tree-length Graphs
- On strong tree-breadth
- On the complexity of computing treebreadth
- On the complexity of computing treelength
- On the complexity of DNA physical mapping
- On the minimum eccentricity shortest path problem
- Safe separators for treewidth
- Spanners for bounded tree-length graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- To approximate treewidth, use treelength!
- Total Ordering Problem
- Tree-decompositions with bags of small diameter
- Treewidth: Characterizations, Applications, and Computations
- Two strikes against perfect phylogeny
Cited in
(13)- On the computational complexity of the rooted subtree prune and regraft distance
- Equivalence between pathbreadth and strong pathbreadth
- On the complexity of computing treebreadth
- Computing Tree-Depth Faster Than 2 n
- Treewidth and the Computational Complexity of MAP Approximations
- On strong tree-breadth
- On the Complexity of Computing Treelength
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- The complexity of bicriteria tree-depth
- Treelength of series-parallel graphs
- Pathlength of outerplanar graphs
- Pathlength of outerplanar graphs
- On the complexity of computing treelength
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 Q1987233)
