Improved approximation for the directed spanner problem
From MaRDI portal
Abstract: We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of , for all k >= 3. This improves the -approximation recently shown by Dinitz and Krauthgamer.
Recommendations
Cites work
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Approximate distance oracles
- Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
- Approximating \(k\)-spanner problems for \(k>2\)
- Compact roundtrip routing in directed networks
- Compact routing with minimum stretch
- Computing almost shortest paths (extended abstract)
- Design networks with bounded pairwise distance
- Directed spanners via flow-based linear programs
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Finding sparser directed spanners
- Generating Sparse 2-Spanners
- Graph Distances in the Data-Stream Model
- Graph spanners
- scientific article; zbMATH DE number 1670859 (Why is no real title available?)
- scientific article; zbMATH DE number 2119746 (Why is no real title available?)
- Improved approximation algorithms for directed Steiner forest
- Lower bounds for local monotonicity reconstruction from transitive-closure spanners
- On sparse spanners of weighted graphs
- On the hardness of approximating spanners
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
- The hardness of approximating spanner problems
- Transitive-closure spanners
- Transitive-closure spanners: a survey
Cited in
(17)- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Approximation algorithms for spanner problems and directed Steiner forest
- Graph spanners: a tutorial review
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Finding sparser directed spanners
- Models and algorithms for network reduction
- Distributed distance-bounded network design through distributed convex programming
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Approximating low-stretch spanners
- Approximating spanners and directed Steiner forest: upper and lower bounds
- Optimal network design with end-to-end service requirements
- New Parameterized Algorithms for APSP in Directed Graphs
- Reachability preservers: new extremal bounds and approximation algorithms
- Approximating spanners and directed Steiner forest. Upper and lower bounds
- Directed spanners via flow-based linear programs
- Approximating the norms of graph spanners
- Roundtrip spanners with (2k-1) stretch
This page was built for publication: Improved approximation for the directed spanner problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012787)
