A space-efficient algorithm for finding strongly connected components

• Tarjan's algorithm for finding strongly connected components is widely used.
• We present an improvement to this algorithm which reduces its space requirements.
• Our algorithm has since been incorporated into the widely used SciPy library.

Tarjan's algorithm for finding the strongly connected components of a directed graph is widely used and acclaimed. His original algorithm required at most v(2+5w)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)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)v(1+3w) bits in the worst case. Furthermore, our algorithm has been independently integrated into the widely-used SciPy library for scientific computing.