Max-stretch reduction for tree spanners
DOI10.1007/S00453-007-9058-XzbMATH Open1141.68052OpenAlexW2623570465MaRDI QIDQ2480904FDOQ2480904
Kazuo Iwama, Masaki Okita, Andrzej Lingas
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
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
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)
Cites Work
- Distributed Computing: A Locality-Sensitive Approach
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- Tree spanners in planar graphs
- On sparse spanners of weighted graphs
- Interval Routing
- Title not available (Why is that?)
- Title not available (Why is that?)
- NP-completeness of minimum spanner problems
- Routing with Improved Communication-Space Trade-Off
- Finding the best shortcut in a geometric network
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (1)
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)
