Using selective path-doubling for parallel shortest-path computations

The author considers parallel shortest-path computations in weighted undirected graphs G=(V,E), where n=|V| and m=|E|. The standard path-doubling algorithms consists of O(log n) phases, where in each phase, for every triple of vertices (u₁, u₂, u₃)∈ V³, she updates the distance between u₁ and u₃ to be no more than the sum of the previous-phase distances between {u ₁, u₂} and {u₂, u ₃}. The work performed in each phase, O(n ³) (linear in the number of triples), is currently the bottleneck in 𝒩𝒞 shortest-paths computations. She introduces a new algorithm that for δ=o(n), considers only O(nδ²) triples. Roughly, the resulting 𝒩𝒞 algorithm performs O˜(nδ²) work and augments E with O˜(nδ) new weighted edges such that between every pair of vertices, there exists a minimum weight path of size (number of edges) O˜(n/δ) (where O˜(f)≡O(f polylog n )). To compute shortest-paths, she applies work-efficient algorithms, where the time depends on the size of shortest paths, to the augmented graph. She obtains a O˜(t) time O ˜(|S|n²+n³/ t²) work deterministic PRAM algorithm for computing shortest-paths form |S| sources to all other vertices, where t⩽n is a parameter. When the ratio of the largest edge weight and the smallest edge weight is n/sup O(polylog/ /sup n)/, the algorithm computes shortest paths. When weights are arbitrary, it computes paths within a factor of 1+n/sup -Ω(polylog/ /sup n)/ of shortest. This improves over previous bounds. She achieves improved O˜(|S|(n ²/t+m)+n³/t ²) work for computing approximate distances to within a factor of (1+∈) (for any fixed ∈)