Distributed Spanner Approximation
From MaRDI portal
Publication:4997324
DOI10.1137/20M1312630zbMath1467.05252MaRDI QIDQ4997324
Michal Dory, Keren Censor-Hillel
Publication date: 29 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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 2 ) 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