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) 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.
%0 Journal Article
%1 Pearce2016SpaceEfficient
%A Pearce, David J.
%D 2016
%J Information Processing Letters
%K 05c40-connectivity 05c85-graph-algorithms scipy
%N 1
%P 47--52
%R 10.1016/j.ipl.2015.08.010
%T A Space-Efficient Algorithm for Finding Strongly Connected Components
%U http://dx.doi.org/10.1016/j.ipl.2015.08.010
%V 116
%X 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) 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.
@article{Pearce2016SpaceEfficient,
abstract = {{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) 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.}},
added-at = {2019-03-01T00:11:50.000+0100},
author = {Pearce, David J.},
biburl = {https://www.bibsonomy.org/bibtex/2b3d091a4efc1641f3399299ad1d1221d/gdmcbain},
citeulike-article-id = {14542386},
citeulike-attachment-1 = {pearce_16_space.pdf; /pdf/user/gdmcbain/article/14542386/1130828/pearce_16_space.pdf; fd7cb55a161f74dcbd5406d4f86eb3af3b6d9f1d},
citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.ipl.2015.08.010},
doi = {10.1016/j.ipl.2015.08.010},
file = {pearce_16_space.pdf},
interhash = {0beba494d1cf1e06ec6e62c41ca07db6},
intrahash = {b3d091a4efc1641f3399299ad1d1221d},
issn = {00200190},
journal = {Information Processing Letters},
keywords = {05c40-connectivity 05c85-graph-algorithms scipy},
month = jan,
number = 1,
pages = {47--52},
posted-at = {2018-03-01 03:18:25},
priority = {5},
timestamp = {2019-03-01T00:11:50.000+0100},
title = {{A Space-Efficient Algorithm for Finding Strongly Connected Components}},
url = {http://dx.doi.org/10.1016/j.ipl.2015.08.010},
volume = 116,
year = 2016
}