More time-work tradeoffs for parallel graph algorithms

Publisher Website
Google Scholar
Abstract
Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes three such algorithms that find the strongly connected components of a directed graph. Two of these algorithms are Las Vegas algorithms that run in O(t) time and do 6(rr3/tz + m) and 6(m7L/t + n3/t3) work, respectively. The thircl is a Monte Carlo algorithm that also runsjn 6(t) time, but does 6(7TL71 + v3/t5) work. The O notation means to ignore logarithmic factors. It is also possible to solve the single source shortest path problem with edge lengths between 1 and L in O((n/p) log n log(pL)) time while doing O(n# log p log(pL)) + 6(7n + n log L) work. Finally, the problem of finding an ear decomposition of a. strongly connected directed graph can be reduced to (he problem of finding a spanning tree with a specified root

This publication has 0 references indexed in Scilit: