Fetching the paper…
Reading the bibliography…
We use exponential start time clustering to design faster and more work-efficient parallel graph algorithms involving distances.
Complexity of network synchronization
Baruch Awerbuch · 1985
Earlier work this paper cites.
Graph spanners
David Peleg and Alejandro A. Schäffer · 1989
Earlier work this paper cites.
Towards a theory of nearly constant time parallel algorithms
Joseph Gil, Yossi Matias, and Uzi Vishkin · 1991
Earlier work this paper cites.
High-probability parallel transitive-closure algorithms
J. Ullman and M. Yannakakis · 1991
Earlier work this paper cites.
A parallel randomized approximation scheme for shortest paths
Philip N Klein and Sairam Sairam · 1992
Earlier work this paper cites.
On sparse spanners of weighted graphs
Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares · 1993
Earlier work this paper cites.
Randomized parallel connectivity
Hillel Gazit · 1993
Earlier work this paper cites.
A graph-theoretic game and its application to the k k -server problem
N. Alon, R. Karp, D. Peleg, and D. West · 1995
Earlier work this paper cites.
Probabilistic approximation of metric spaces and its algorithmic applications
Yair Bartal · 1996
Earlier work this paper cites.
A randomized parallel algorithm for single-source shortest paths
Philip N Klein and Sairam Subramanian · 1997
Earlier work this paper cites.
Fast algorithms for constructing t-spanners and paths with stretch t
Edith Cohen · 1998
Cited alongside, same era.
Timework tradeoffs of the single-source shortest paths problem
Hanmao Shi and Thomas H. Spencer · 1999
Cited alongside, same era.
Polylog-time and near-linear work approximation scheme for undirected shortest paths
Edith Cohen · 2000
Cited alongside, same era.
All-pairs almost shortest paths
Dorit Dor, Shay Halperin, and Uri Zwick · 2000
Cited alongside, same era.
New constructions of ( α , β ) (\alpha,\beta) -spanners and purely additive spanners
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie · 2005
Cited alongside, same era.
Approximate distance oracles
Mikkel Thorup and Uri Zwick · 2005
Cited alongside, same era.
Distributed algorithms for ultrasparse spanners and linear size skeletons
Seth Pettie · 2008
Later among the works it cites.
Additive spanners and ( α \alpha , β \beta )-spanners
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie · 2010
Later among the works it cites.
A model of computation for mapreduce
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii · 2010
Later among the works it cites.
Parallel graph decompositions using random shifts
Gary L. Miller, Richard Peng, and Shen Chen Xu · 2013
Closest in time.
Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan · 2014
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
Surender Baswana and Sandeep Sen · 2007
Cited alongside, same era.
Deterministic distributed construction of linear stretch spanners in polylogarithmic time
Bilel Derbel, Cyril Gavoille, and David Peleg · 2007
Cited alongside, same era.
On the locality of distributed sparse spanner construction
Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot · 2008
Cited alongside, same era.
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, and Shen Chen Xu · 2014
Closest in time.
Simple parallel and distributed algorithms for spectral graph sparsification
Ioannis Koutis · 2014
Closest in time.
Improved parallel algorithms for spanners and hopsets
Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu · 2014
Closest in time.
A simple and practical linear-work parallel algorithm for connectivity
Julian Shun, Laxman Dhulipala, and Guy Blelloch · 2014
Closest in time.