Concurrent algorithm for strongly connected components (SCCs) Is anybody aware of a concurrent version of Tarjan's SCCs algorithm, Kosaraju's algorithm or any other fast, O(|V| + |E|) algorithm for finding SCCs? Neither of those algorithms seem to be very hard to multithread, but I'd be happy for somebody else to have done this job. What I'm trying to handle here is an 8 GB directed graph, which I keep in RAM using a big AWS instance, and I'd like to make a good use of all 16 cores.
This answer might come late, but there's a work by Gavin Lowe: "Concurrent Depth-First Search Algorithms", Proceedings of TACAS 2014, p. 202--216, Volume 8413 of LNCS, Springer that has descriptions for parallel algorithms for computing strongly connected components, lasso-shaped paths and finding nodes that are part of a cycle.