An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs
DOI10.1007/S00453-013-9765-4zbMATH Open1303.05186OpenAlexW2012939398MaRDI QIDQ472490FDOQ472490
Authors: Feodor F. Dragan, Ekkehard Köhler 
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
Recommendations
approximation algorithmsgraph algorithmsbalanced separatorsgeneralized chordal graphsminimum max-stretch spanning tree problemRobertson-Seymour's tree-decompositiontree \(t\)-spanner problem
Cites Work
- Graph Classes: A Survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Low complexity variants of the arrow distributed directory
- Tree spanners on chordal graphs: complexity and algorithms
- Spanners for bounded tree-length graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Tree Spanners
- Tree spanners in planar graphs
- On the Desirability of Acyclic Database Schemes
- On the complexity of computing treelength
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- A Separator Theorem for Chordal Graphs
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Title not available (Why is that?)
- A characterisation of rigid circuit graphs
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Spanners in sparse graphs
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Additive Tree Spanners
- Approximation algorithms for embedding general metrics into trees
- Lower-Stretch Spanning Trees
- Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
- A note on distance approximating trees in graphs
- Tree-decompositions with bags of small diameter
- The zoo of tree spanner problems
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Title not available (Why is that?)
- Approximating \(k\)-spanner problems for \(k>2\)
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- Dynamic analysis of the arrow distributed protocol
- Tree spanners for bipartite graphs and probe interval graphs
Cited In (21)
- Computing the union join and subset graph of acyclic hypergraphs in subquadratic time
- Treewidth versus clique number. II: Tree-independence number
- Injective hulls of various graph classes
- 3-colouring for dually chordal graphs and generalisations
- On approximating tree spanners that are breadth first search trees
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Approximating minimum MAX-stretch spanning trees on unweighted graphs
- Tree 3-spanners on generalized prisms of graphs
- Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
- On the complexity of computing treebreadth
- On the complexity of computing treebreadth
- Graphs with minimum spanner \(\varsigma(G)\geq2\rho-1\)
- On strong tree-breadth
- Tree spanners of bounded degree graphs
- Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
- Polynomial algorithms for sparse spanners on subcubic graphs
- Title not available (Why is that?)
- Helly-gap of a graph and vertex eccentricities
- A short note on the complexity of computing strong pathbreadth
- Treelength of series-parallel graphs
- Line-distortion, bandwidth and path-length of a graph
This page was built for publication: An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472490)
