# Parallel Graph Decompositions Using Random Shifts

arXiv: https://arxiv.org/abs/1307.3692 · HTML: https://mlsanity.com/paper/1307.3692/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2013.

## Built on by (most cited first, 2 of 2)

- [Graph Learning and Its Advancements on Large Language Models: A Holistic Survey](https://mlsanity.com/paper/2212.08966/) (2022)
- [The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering](https://mlsanity.com/paper/2411.10290/) (2024)

## Abstract (arXiv)

We show an improved parallel algorithm for decomposing an undirected unweighted graph into small diameter pieces with a small fraction of the edges in between. These decompositions form critical subroutines in a number of graph algorithms. Our algorithm builds upon the shifted shortest path approach introduced in [Blelloch, Gupta, Koutis, Miller, Peng, Tangwongsan, SPAA 2011]. By combining various stages of the previous algorithm, we obtain a significantly simpler algorithm with the same asymptotic guarantees as the best sequential algorithm.