Parallel graph decompositions using random shifts
Proceedings of the twenty-fifth annual ACM symposium on Parallelism in …, 2013•dl.acm.org
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 …
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 …
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.
ACM Digital Library