On the complexity of computing treebreadth
DOI10.1007/s00453-019-00657-7zbMath1433.68168OpenAlexW2995929903MaRDI QIDQ1987233
Sylvain Legay, Nicolas Nisse, Guillaume Ducoffe
Publication date: 14 April 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-02528905/file/DLN-AlgorithmicaRevised_submitted.pdf
graph theoryplanar graphsNP-completenessbipartite graphspathlengthpathbreadthRobertson and Seymour's tree decompositiontreebreadth
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 (2)
Cites Work
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Safe separators for treewidth
- On the complexity of computing treelength
- On the complexity of DNA physical mapping
- Characterizations and algorithmic applications of chordal graph embeddings
- Listing all potential maximal cliques of a graph
- An introduction to clique minimal separator decomposition
- A short note on the complexity of computing strong pathbreadth
- Algorithmic graph theory and perfect graphs
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- 3-colouring for dually chordal graphs and generalisations
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Complexity of Computing Treebreadth
- Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
- On Strong Tree-Breadth
- 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
- Total Ordering Problem
- Dually Chordal Graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Two strikes against perfect phylogeny
- Metric Dimension of Bounded Tree-length Graphs
- Better Approximation Algorithms for the Graph Diameter
- 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
