Approximating low-stretch spanners

DOI10.1137/1.9781611974331.CH59MaRDI QIDQ4575638zbMATH OpenOpenAlexFDO

Authors Michael Dinitz, Ze Yu Zhang

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Directed spanners via flow-based linear programs
• Improved approximation for the directed spanner problem
• Fault-tolerant spanners
• scientific article; zbMATH DE number 1757950
• scientific article; zbMATH DE number 6696497

Cited in

(14)

• Graph spanners: a tutorial review
• Lasserre integrality gaps for graph spanners and related problems
• Deformable spanners and applications
• Approximating approximate distance oracles
• Distributed spanner approximation
• The norms of graph spanners
• Small Stretch Pairwise Spanners
• Directed spanners via flow-based linear programs
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• Approximating the norms of graph spanners
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Spanner approximations in practice
• Approximation algorithms for directed weighted spanners
• Directed buy-at-bulk spanners

This page was built for publication: Approximating low-stretch spanners

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