An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
From MaRDI portal
Publication:3088092
DOI10.1007/978-3-642-22935-0_15zbMath1343.05149OpenAlexW1860059046MaRDI QIDQ3088092
Feodor F. Dragan, Ekkehard Köhler
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_15
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Swapping labeled tokens on graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Spanners in sparse graphs
- Tree spanners for bipartite graphs and probe interval graphs
- On the complexity of computing treelength
- 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
- The zoo of tree spanner problems
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A Separator Theorem for Chordal Graphs
- Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
- Lower-Stretch Spanning Trees
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- 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