A Space Efficient Algorithm for Detecting Strongly Connected Components

Author(s). David J. Pearce.

Venue. In Information Processing Letters, 116 (1), pages 47--52, 2016. ©Elsevier

Abstract. Tarjan’s algorihm for finding the strongly connected components of a directed graph is widely used and acclaimed. His original algorithm required at most v(2 + 5w) bits of storage, where w is the machine’s word size, whilst Nuutila and Soisalon-Soininen reduced this to v(1 + 4w). Many real world applications routinely operate on very large graphs where the storage requirements of such algorithms is a concern. We present a novel improvement on Tarjan’s algorithm which reduces the space requirements to v(1 + 3w) bits in the worst case. Furthermore, our algorithm has been independently integrated into the widely-used SciPy library for scientific computing.

Notes. This algorithm was incorporated into SciPy, a widely used Python Library for scientific computing (see here). Some discussion of the SciPy implementation can be found here as well. A straightforward Java implementation of the algorithm is available here and another C++ implementation is available here.