Distributed Spanner Approximation

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W15: Distributed algorithms

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Approximating \(k\)-spanner problems for \(k>2\)
On the distributional complexity of disjointness
Approximation algorithms for combinatorial problems
On the ratio of optimal integral and fractional covers
Low diameter graph decompositions
A fast network-decomposition algorithm and its applications to constant-time distributed computation
Near-linear lower bounds for distributed distance computations, even in sparse networks
Approximation algorithms for spanner problems and directed Steiner forest
Sublinear fully distributed partition with applications
The hardness of approximating spanner problems
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
Finding sparser directed spanners
Optimal distributed all pairs shortest paths and applications
On the locality of distributed sparse spanner construction
Fault-tolerant spanners
On the power of the congested clique model
Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
Local Computation
Distributed Distance-Bounded Network Design Through Distributed Convex Programming
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
Approximate distance oracles
Graph spanners
A Greedy Heuristic for the Set-Covering Problem
Locality in Distributed Graph Algorithms
Routing with Polynomial Communication-Space Trade-Off
Generating Low-Degree 2-Spanners
Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
Generating Sparse 2-Spanners
A new series of dense graphs of high girth
Distributed Computing: A Locality-Sensitive Approach
Approximating Low-Stretch Spanners
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
A trade-off between space and efficiency for routing tables
A Fast Parametric Maximum Flow Algorithm and Applications
An Optimal Synchronizer for the Hypercube
Communication Complexity
Distributed Verification and Hardness of Distributed Approximation
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
Roundtrip spanners and roundtrip routing in directed graphs
On the complexity of local distributed graph problems
Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
An efficient distributed algorithm for constructing small dominating sets
Polylogarithmic-time deterministic network decomposition and distributed derandomization
Hardness of Distributed Optimization
Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
Compact routing schemes with improved stretch
Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
An optimal distributed (Δ+1)-coloring algorithm?
A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
Distributed (∆+1)-coloring in sublogarithmic rounds
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
Directed spanners via flow-based linear programs
Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
Automata, Languages and Programming
Constant-time distributed dominating set approximation
Computing almost shortest paths
Distributed construction of purely additive spanners
Distributed algorithms for ultrasparse spanners and linear size skeletons
On the hardness of approximating spanners