Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs

DOI10.1137/060666202zbMath1181.05023OpenAlexW1985209733MaRDI QIDQ3642863

Yuval Emek, David Peleg

Publication date: 6 November 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060666202

zbMATH Keywords

distancespanning treespannerlow stretch

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On approximating tree spanners that are breadth first search trees ⋮ A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ Better hardness results for the minimum spanning tree congestion problem ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Spanners in sparse graphs ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ An improved algorithm for computing all the best swap edges of a tree spanner ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Graph spanners: a tutorial review ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem ⋮ Swapping labeled tokens on graphs ⋮ An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner