A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
From MaRDI portal
Publication:5297139
DOI10.1002/rsa.20130zbMath1118.68582OpenAlexW4231761369MaRDI QIDQ5297139
Publication date: 18 July 2007
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20130
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (34)
Sparse hop spanners for unit disk graphs ⋮ A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Distributed distance computation and routing with small messages ⋮ Relaxed spanners for directed disk graphs ⋮ New pairwise spanners ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Faster cut sparsification of weighted graphs ⋮ On dynamic shortest paths problems ⋮ Unnamed Item ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Streaming algorithm for graph spanners-single pass and constant processing time per edge ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Approximating Shortest Paths in Graphs ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Constructing light spanners deterministically in near-linear time ⋮ Distributed Spanner Approximation ⋮ On the Complexity of Universal Leader Election ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Near-Optimal Distributed Maximum Flow
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Complexity of network synchronization
- Parallel linear programming in fixed dimension almost surely in constant time
- A trade-off between space and efficiency for routing tables
- Algorithms – ESA 2004
- Algorithms – ESA 2005
- STACS 2005
- Automata, Languages and Programming
This page was built for publication: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
