| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427087 | Information Processing Letters | 2016 | 6 Pages |
•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.
