Parallel Graph Decompositions Using Random Shifts

Abstract

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.

References in corpus (1)

• Nearly Tight Low Stretch Spanning Trees

Cited by in corpus (9)

• Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
• Improved Parallel Algorithms for Spanners and Hopsets
• Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
• The Energy Complexity of Broadcast
• Random Rates for 0-Extension and Low-Diameter Decompositions
• A Fast Algorithm for Source-wise Round-trip Spanners
• The Energy Complexity of BFS in Radio Networks
• Implicit Decomposition for Write-Efficient Connectivity Algorithms
• Space and Time Efficient Parallel Graph Decomposition, Clustering, and Diameter Approximation