Abstract:
The standard serial algorithm for strongly connected components is based on depth first search, which is difficult to parallelize. We describe a divide-and-conquer algorithm for this problem which has significantly greater potential for parallelization. For a graph with $n$ vertices in which degrees are bounded by a constant, we show the expected serial running time of our algorithm to be O(n log n).