The zoo of tree spanner problems

DOI10.1016/J.DAM.2007.07.001MaRDI QIDQ2476246zbMATH OpenOpenAlexFDO

Authors 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

complexityfundamental cycle basesstretch factor

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27)

Recommendations

• Tree Spanners
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• scientific article; zbMATH DE number 1262806
• scientific article; zbMATH DE number 1696535
• Tree spanners in planar graphs

Cites work

• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Additive Tree Spanners
• Algorithms for Generating Fundamental Cycles in a Graph
• Approximating minimum MAX-stretch spanning trees on unweighted graphs
• Approximation algorithms for the shortest total path length spanning tree problem
• Approximation and Online Algorithms
• Automata, Languages and Programming
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1947056 (Why is no real title available?)
• scientific article; zbMATH DE number 2080984 (Why is no real title available?)
• Lower-stretch spanning trees
• MAD trees and distance-hereditary graphs
• On finding a cycle basis with a shortest maximal cycle
• On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
• On the minimum diameter spanning tree problem
• Optimum Communication Spanning Trees
• The complexity of the network design problem
• Tree Spanners
• Tree spanners for bipartite graphs and probe interval graphs.
• Tree spanners in planar graphs
• Tree spanners on chordal graphs: complexity and algorithms

Cited in

(16)

• 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
• 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
• An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
• Lower bounds for strictly fundamental cycle bases in grid graphs
• General variable neighborhood search for the minimum stretch spanning tree problem
• Carousel greedy algorithms for the minimum stretch spanning tree problem
• Tree t-spanners for edge adjacency distances
• Combinatorial network abstraction by trees and distances
• Minimum cut bases in undirected networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476246)