Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
From MaRDI portal
Publication:2375302
DOI10.1007/s00446-005-0147-2zbMath1266.68212MaRDI QIDQ2375302
Publication date: 13 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-005-0147-2
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
68W15: Distributed algorithms
Related Items
Optimal Network Design with End-to-End Service Requirements, Unnamed Item, The Greedy Spanner Is Existentially Optimal, Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models, A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths, The Sparsest Additive Spanner via Multiple Weighted BFS Trees, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, Distributed construction of purely additive spanners, Distributed algorithms for ultrasparse spanners and linear size skeletons, Improved weighted additive spanners, Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions, Models and algorithms for network reduction, Some results on approximate 1-median selection in metric spaces, Graph spanners: a tutorial review, Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC, Light spanners for high dimensional norms via stochastic decompositions, The sparsest additive spanner via multiple weighted BFS trees, COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- The space complexity of approximating the frequency moments
- All pairs shortest paths for graphs with small integer length edges
- On finding common neighborhoods in massive graphs.
- All-Pairs Small-Stretch Paths
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Better streaming algorithms for clustering problems
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- Graph spanners
- Routing with Polynomial Communication-Space Trade-Off
- The Probabilistic Communication Complexity of Set Intersection
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Distributed Computing: A Locality-Sensitive Approach
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- An Approximate L1 -Difference Algorithm for Massive Data Streams
- All-Pairs Almost Shortest Paths
- (1 + εΒ) -spanner constructions for general graphs
- Automata, Languages and Programming
- Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
- Computing almost shortest paths
