Fast deterministic distributed algorithms for sparse spanners
From MaRDI portal
Publication:930906
DOI10.1016/j.tcs.2008.02.019zbMath1165.68065MaRDI QIDQ930906
Publication date: 24 June 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (6)
The sparsest additive spanner via multiple weighted BFS trees ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Congested Clique Algorithms for Graph Spanners
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast distributed network decompositions and covers
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- On the ratio of optimal integral and fractional covers
- Simple and efficient network decomposition and synchronization
- A distributed algorithm to find \(k\)-dominating sets
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Compact Routing with Minimum Stretch
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Approximate distance oracles
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- The price of being near-sighted
- Deterministic coin tossing with applications to optimal parallel list ranking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Complexity of network synchronization
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Distributed Computing: A Locality-Sensitive Approach
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Compact routing schemes with low stretch factor
- Distance labeling in graphs
- On the Complexity of Distributed Network Decomposition
- Distributed Computing
- Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
- What cannot be computed locally!
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Automata, Languages and Programming
- Distributed MST for constant diameter graphs
- Computing almost shortest paths
This page was built for publication: Fast deterministic distributed algorithms for sparse spanners
