The zoo of tree spanner problems

DOI10.1016/j.dam.2007.07.001zbMath1176.90504MaRDI QIDQ2476246

Christian Liebchen, Gregor Wünsch

Publication date: 18 March 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.07.001

zbMATH Keywords

complexity; stretch factor; fundamental cycle bases

Mathematics Subject Classification ID

05C05: Trees

90C27: Combinatorial optimization

Related Items

Lower bounds for strictly fundamental cycle bases in grid graphs, An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner, General variable neighborhood search for the minimum stretch spanning tree problem, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, On minimum average stretch spanning trees in grid graphs, Minimum cut bases in undirected networks, An improved algorithm for computing all the best swap edges of a tree spanner, The minimum stretch spanning tree problem for typical graphs, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, On minimum average stretch spanning trees in polygonal 2-trees, Optimality computation of the minimum stretch spanning tree problem, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, A Faster Computation of All the Best Swap Edges of a Tree Spanner

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the minimum diameter spanning tree problem
• On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
• On finding a cycle basis with a shortest maximal cycle
• MAD trees and distance-hereditary graphs
• Approximation algorithms for the shortest total path length spanning tree problem
• Tree spanners on chordal graphs: complexity and algorithms
• Optimum Communication Spanning Trees
• Lower-stretch spanning trees
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• The complexity of the network design problem
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Additive Tree Spanners
• Tree Spanners
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Automata, Languages and Programming
• Approximation and Online Algorithms
• Graph-Theoretic Concepts in Computer Science
• Tree spanners in planar graphs