%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 }