An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
From MaRDI portal
Publication:472490
DOI10.1007/s00453-013-9765-4zbMath1303.05186OpenAlexW2012939398MaRDI QIDQ472490
Ekkehard Köhler, Feodor F. Dragan
Publication date: 19 November 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9765-4
graph algorithmsapproximation algorithmsbalanced separatorsgeneralized chordal graphsminimum max-stretch spanning tree problemRobertson-Seymour's tree-decompositiontree \(t\)-spanner problem
Related Items (15)
On approximating tree spanners that are breadth first search trees ⋮ Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ Injective hulls of various graph classes ⋮ 3-colouring for dually chordal graphs and generalisations ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Treelength of series-parallel graphs ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Tree spanners of bounded degree graphs ⋮ On Strong Tree-Breadth ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ A short note on the complexity of computing strong pathbreadth ⋮ On the complexity of computing treebreadth ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ On the Complexity of Computing Treebreadth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating \(k\)-spanner problems for \(k>2\)
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- Spanners in sparse graphs
- Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
- Dynamic analysis of the arrow distributed protocol
- Tree spanners for bipartite graphs and probe interval graphs
- On the complexity of computing treelength
- A note on distance approximating trees in graphs
- Low complexity variants of the arrow distributed directory
- A characterisation of rigid circuit graphs
- Tree spanners on chordal graphs: complexity and algorithms
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- The zoo of tree spanner problems
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- On the Desirability of Acyclic Database Schemes
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- A Separator Theorem for Chordal Graphs
- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Lower-Stretch Spanning Trees
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Graph Classes: A Survey
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Additive Tree Spanners
- Tree Spanners
- Tree spanners in planar graphs
This page was built for publication: An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
