Parallel Graph Decompositions Using Random Shifts

An introduction to probability theory and its applications. Vol. II

W. Feller · 1971

Earlier work this paper cites.

Complexity of network synchronization

B. Awerbuch · 1985

Earlier work this paper cites.

Network decomposition and locality in distributed computation (extended abstract)

B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin · 1989

Earlier work this paper cites.

Decomposing graphs into regions of small diameter

N. Linial and M. Saks · 1991

Earlier work this paper cites.

Low-diameter graph decomposition is in NC

B. Awerbuch, B. Berger, L. Cowen, and D. Peleg · 1992

Earlier work this paper cites.

Shallow excluded minors and improved graph decompositions

S. Plotkin, S. Rao, and W. D. Smith · 1994

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

Y. Bartal · 1996

Earlier work this paper cites.

A randomized parallel algorithm for single-source shortest paths

P. N. Klein and S. Subramanian · 1997

Earlier work this paper cites.

The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms

D. E. Knuth · 1997

Earlier work this paper cites.

Normalized cuts and image segmentation

J. Shi and J. Malik · 1997

Cited alongside, same era.

Fast algorithms for constructing t-spanners and paths with stretch t

E. Cohen · 1998

Cited alongside, same era.

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

T. Leighton and S. Rao · 1999

Cited alongside, same era.

Polylog-time and near-linear work approximation scheme for undirected shortest paths

E. Cohen · 2000

Cited alongside, same era.

Probability and statistics with reliability, queuing and computer science applications

K. S. Trivedi · 2002

Cited alongside, same era.

A tight bound on approximating arbitrary metrics by tree metrics

J. Fakcharoenphol, S. Rao, and K. Talwar · 2004

Cited alongside, same era.

Breaking the multicommodity flow barrier for O ⁡ ( l ​ o ​ g ​ n ) {O}(\sqrt{logn}) -approximations to sparsest cut

J. Sherman · 2009

Later among the works it cites.

A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers)

C. E. Leiserson and T. B. Schardl · 2010

Later among the works it cites.

Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

P. Christiano, J. A. Kelner, A. Ma̧dry, D. Spielman, and S.-H. Teng · 2011

Later among the works it cites.

Separator theorems for minor-free and shallow minor-free graphs with applications

C. Wulff-Nilsen · 2011

Later among the works it cites.

Using petal-decompositions to build a low stretch spanning tree

I. Abraham and O. Neiman · 2012

Later among the works it cites.

Direction-optimizing breadth-first search