To Approximate Treewidth, Use Treelength!
From MaRDI portal
Publication:5741086
DOI10.1137/15M1034039zbMath1341.05238OpenAlexW2478689417MaRDI QIDQ5741086
David Coudert, Guillaume Ducoffe, Nicolas Nisse
Publication date: 22 July 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1034039
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Obstructions to a small hyperbolicity in Helly graphs, Data center interconnection networks are not hyperbolic, On the hyperbolicity of bipartite graphs and intersection graphs, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, Treelength of series-parallel graphs, A short note on the complexity of computing strong pathbreadth, On the complexity of computing treebreadth, On distance-preserving elimination orderings in graphs: complexity and algorithms, On the Complexity of Computing Treebreadth
Cites Work
- Unnamed Item
- Unnamed Item
- The decomposition of graphs into \(k\)-connected components
- Connected tree-width
- Finding the longest isometric cycle in a graph
- On the complexity of computing treelength
- Connected cutsets of a graph and triangle bases of the cycle space
- A partial k-arboretum of graphs with bounded treewidth
- On finding a cycle basis with a shortest maximal cycle
- Characterizations and algorithmic applications of chordal graph embeddings
- Vertex-to-vertex pursuit in a graph
- Contraction obstructions for treewidth
- Tree-decompositions with bags of small diameter
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On the Tree-Width of Planar Graphs
- Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
- Metric Dimension of Bounded Width Graphs
- Weakly Modular Graphs and Nonpositive Curvature
- The Bidimensional Theory of Bounded-Genus Graphs
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Packing and Covering δ-Hyperbolic Spaces by Balls
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
- Tree decompositions and social graphs
