Max-stretch reduction for tree spanners

DOI10.1007/S00453-007-9058-XzbMATH Open1141.68052OpenAlexW2623570465MaRDI QIDQ2480904FDOQ2480904

Authors Kazuo Iwama, Andrzej Lingas, Masaki Okita 

Publication date 3 April 2008

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9058-x

zbMATH Keywords

Time complexityGraph augmentationMaximum stretchTree spanner

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algorithms and Data Structures
• On the approximability of some maximum spanning tree problems
• On the approximability of some Maximum Spanning Tree Problems
• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• Approximating minimum MAX-stretch spanning trees on unweighted graphs
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Maximizing spanning trees in almost complete graphs
• Maximizing spanning trees in almost complete graphs
• scientific article; zbMATH DE number 2011838
• Optimality computation of the minimum stretch spanning tree problem

Cites work

• scientific article; zbMATH DE number 2080232 (Why is no real title available?)
• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• scientific article; zbMATH DE number 1420896 (Why is no real title available?)
• scientific article; zbMATH DE number 6472642 (Why is no real title available?)
• An Optimal Synchronizer for the Hypercube
• Approximating minimum MAX-stretch spanning trees on unweighted graphs
• Distributed Computing: A Locality-Sensitive Approach
• Finding the best shortcut in a geometric network
• Interval Routing
• NP-completeness of minimum spanner problems
• On sparse spanners of weighted graphs
• Routing with Improved Communication-Space Trade-Off
• Tree Spanners
• Tree spanners in planar graphs

Cited in

(1)

• Algorithms and Data Structures

This page was built for publication: Max-stretch reduction for tree spanners

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