The zoo of tree spanner problems
From MaRDI portal
Publication:2476246
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
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