The zoo of tree spanner problems

DOI10.1016/j.dam.2007.07.001zbMath1176.90504OpenAlexW1973029334MaRDI 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

complexitystretch factorfundamental cycle bases

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27)

Related Items (13)

A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ 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 ⋮ An improved algorithm for computing all the best swap edges of a tree spanner ⋮ On minimum average stretch spanning trees in grid graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Minimum cut bases in undirected networks ⋮ Lower bounds for strictly fundamental cycle bases in grid graphs ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ On minimum average stretch spanning trees in polygonal 2-trees ⋮ An Improved Algorithm for Computing 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

This page was built for publication: The zoo of tree spanner problems