Distributed algorithms for ultrasparse spanners and linear size skeletons
From MaRDI portal
Publication:5919900
DOI10.1007/s00446-009-0091-7zbMath1267.68314MaRDI QIDQ5919900
Publication date: 28 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-009-0091-7
Related Items
Distributed construction of purely additive spanners, Can we locally compute sparse connected subgraphs?, Rumor Spreading with No Dependence on Conductance, Constructing near spanning trees with few local inspections
Cites Work
- Unnamed Item
- Unnamed Item
- Fast deterministic distributed algorithms for sparse spanners
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Ramsey partitions and proximity data structures
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- On sparse spanners of weighted graphs
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Compact Routing with Minimum Stretch
- On the locality of distributed sparse spanner construction
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Additive spanners and (α, β)-spanners
- Geometric Spanner Networks
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Local Computation of Nearly Additive Spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Distributed Computing: A Locality-Sensitive Approach
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- A trade-off between space and efficiency for routing tables
- Compact roundtrip routing in directed networks
- Distance labeling in graphs
- All-Pairs Almost Shortest Paths
- Compact name-independent routing with minimum stretch
- (1 + εΒ) -spanner constructions for general graphs
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- Low Distortion Spanners
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
- Algorithms – ESA 2004
- Automata, Languages and Programming
- Computing almost shortest paths
