Improved Approximation for the Directed Spanner Problem
From MaRDI portal
Publication:3012787
DOI10.1007/978-3-642-22006-7_1zbMath1332.68283arXiv1012.4062OpenAlexW2144474663MaRDI QIDQ3012787
Grigory Yaroslavtsev, Sofya Raskhodnikova, Piotr Berman, Konstantin Makarychev, Arnab Bhattacharyya
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.4062
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Models and algorithms for network reduction ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Optimal Network Design with End-to-End Service Requirements ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Graph spanners: a tutorial review ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- Approximating \(k\)-spanner problems for \(k>2\)
- On sparse spanners of weighted graphs
- The hardness of approximating spanner problems
- Compact Routing with Minimum Stretch
- Design networks with bounded pairwise distance
- Finding sparser directed spanners
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Approximate distance oracles
- Graph Distances in the Data-Stream Model
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Generating Sparse 2-Spanners
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Compact roundtrip routing in directed networks
- Transitive-Closure Spanners
- Transitive-Closure Spanners: A Survey
- Directed spanners via flow-based linear programs
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
- Computing almost shortest paths
- Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
- On the hardness of approximating spanners
