<p>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.</p>

CC BY-SA 3.0
2015-01-09T18:18:29.897Z
The implementation is here: http://www.cs.ox.ac.uk/people/gavin.lowe/parallelDFS.html (This is mentioned in the paper, but the paper appears to be behind a pay-wall.)
Radu GRIGore
CC BY-SA 3.0
2015-01-09T17:12:28.243Z
2015-01-09T17:12:28.243Z
Antti
<p>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.</p>

<ds.algorithms><graph-algorithms><ds.data-structures>
Concurrent algorithm for strongly connected components (SCCs)
picrin
# Concurrent algorithm for strongly connected components (SCCs)

(Asked by: username_0 on 2013-11-04)

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.

**Tags:** ds.algorithms, graph-algorithms, ds.data-structures


---

## 1 answers

### Answer by username_1 on 2015-01-09. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_2**: The implementation is here: http://www.cs.ox.ac.uk/people/gavin.lowe/parallelDFS.html (This is mentioned in the paper, but the paper appears to be behind a pay-wall.)  

---

