An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

DOI10.1007/978-3-642-22935-0_15zbMath1343.05149MaRDI 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

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

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