Max-stretch reduction for tree spanners

DOI10.1007/s00453-007-9058-xzbMath1141.68052OpenAlexW2623570465MaRDI QIDQ2480904

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

zbMATH Keywords

Time complexityGraph augmentationMaximum stretchTree spanner

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On sparse spanners of weighted graphs
• NP-completeness of minimum spanner problems
• Interval Routing
• Distributed Computing: A Locality-Sensitive Approach
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Finding the best shortcut in a geometric network
• Routing with Improved Communication-Space Trade-Off
• Tree spanners in planar graphs

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