article · ACM Journal of Experimental Algorithmics · 2012
A topological sorting algorithm for large graphs
Deepak Ajwani, Adan Cosgaya-Lozano, Norbert Zeh
Cited by 16Abstract and details only
Abstract
We present an I/O-efficient algorithm for topologically sorting directed acyclic graphs, called IterTS. In the worst case, our algorithm is extremely inefficient and performs O( n ċ sort( m )) I/Os. However, our experiments show that IterTS achieves good performance in practice. To evaluate IterTS, we compared its running time to those of three competitors: PeelTS, an I/O-efficient implementation of the standard strategy of iteratively removing sources and sinks; ReachTS, an I/O-efficient implementation of a recent parallel divide-and-conquer algorithm based on reachability queries; and SeTS, a standard DFS-based topological sorting built on top of a semiexternal DFS algorithm. In our evaluation on various types of input graphs, IterTS consistently outperformed PeelTS and ReachTS by at least an order of magnitude in most cases. SeTS outperformed IterTS on most graphs whose vertex sets fit in memory. However, IterTS often came close to the running time of SeTS on these inputs and, more importantly, SeTS was not able to process graphs whose vertex sets were beyond the size of main memory, while IterTS was able to process such inputs efficiently.
Cite this paper
Ajwani, D., Cosgaya-Lozano, A., & Zeh, N. (2012). A topological sorting algorithm for large graphs. ACM Journal of Experimental Algorithmics, 17. https://doi.org/10.1145/2133803.2330083
Ajwani, Deepak, et al. “A topological sorting algorithm for large graphs.” ACM Journal of Experimental Algorithmics, vol. 17, 2012, https://doi.org/10.1145/2133803.2330083.
Ajwani, Deepak, Adan Cosgaya-Lozano, and Norbert Zeh. 2012. “A topological sorting algorithm for large graphs.” ACM Journal of Experimental Algorithmics 17. https://doi.org/10.1145/2133803.2330083.
Ajwani, D., Cosgaya-Lozano, A. and Zeh, N. (2012) ‘A topological sorting algorithm for large graphs’, ACM Journal of Experimental Algorithmics, 17. Available at: https://doi.org/10.1145/2133803.2330083.
@article{ajwani2012topological,
title = {{A topological sorting algorithm for large graphs}},
author = {Ajwani, Deepak and Cosgaya-Lozano, Adan and Zeh, Norbert},
journal = {ACM Journal of Experimental Algorithmics},
volume = {17},
year = {2012},
doi = {10.1145/2133803.2330083}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.