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.