Fast deterministic distributed algorithms for sparse spanners

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