Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

DOI10.1137/1.9781611974782.34zbMath1410.68290arXiv1607.06068OpenAlexW2486585506MaRDI QIDQ4575771

Eden Chlamtáč, Bundit Laekhanukit, Michael Dinitz, Guy Kortsarz

Publication date: 16 July 2018

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

Full work available at URL: https://arxiv.org/abs/1607.06068

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Parameterized complexity of directed spanner problems ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ Graph spanners: a tutorial review ⋮ Distance-Preserving Graph Contractions ⋮ Distributed Spanner Approximation ⋮ Distance-Preserving Graph Contractions ⋮ Lasserre integrality gaps for graph spanners and related problems