### Abstract

The main advantages of Tarjan's strongly connected component (SCC) algorithm are its linear time complexity and ability to return SCCs on-the-fly, while traversing or even generating the graph. Until now, most parallel SCC algorithms sacrifice both: they run in quadratic worst-case time and/or require the full graph in advance.
The current paper presents a novel parallel, on-the-fly SCC algorithm. It preserves the linear-time property by letting workers explore the graph randomly while carefully communicating partially completed SCCs. We prove that this strategy is correct. For efficiently communicating partial SCCs, we develop a concurrent, iterable disjoint set structure (combining the union-find data structure with a cyclic list).
We demonstrate scalability on a 64-core machine using 75 real-world graphs (from model checking and explicit data graphs), synthetic graphs (combinations of trees, cycles and linear graphs), and random graphs. Previous work did not show speedups for graphs containing a large SCC. We observe that our parallel algorithm is typically 10-30× faster compared to Tarjan's algorithm for graphs containing a large SCC. Comparable performance (with respect to the current state-of-the-art) is obtained for graphs containing many small SCCs.

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 |

Place of Publication | New York |

Publisher | Association for Computing Machinery (ACM) |

Pages | 8 |

Number of pages | 12 |

ISBN (Print) | 978-1-4503-4092-2 |

DOIs | |

Publication status | Published - Mar 2016 |

### Publication series

Name | |
---|---|

Publisher | ACM |

### Keywords

- keywords strongly connected components
- union-find
- depth first search
- EWI-26873
- Parallel
- METIS-316845
- Multi-Core
- Graph
- Digraph
- SCC
- IR-99728
- Algorithm

## Cite this

Bloemen, V., Laarman, A., & van de Pol, J. C. (2016). Multi-Core On-The-Fly SCC Decomposition. In

*Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016*(pp. 8). New York: Association for Computing Machinery (ACM). https://doi.org/10.1145/2851141.2851161