External topological sorting in large graphs

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2018, 10827 LNCS pp. 203 - 220
Issue Date:
Filename Description Size
468305_Print.indd_paper.pdfPublished version491.73 kB
Adobe PDF
Full metadata record
© Springer International Publishing AG, part of Springer Nature 2018. Topological sorting is a fundamental problem in graph analysis. Given the fact that real world graphs grow rapidly so that they cannot entirely reside in main memory, in this paper, we study external memory algorithms for the topological sorting problem. We propose a contraction-expansion paradigm and devise an external memory algorithm based on the paradigm for the topological sorting problem. Our new algorithm is efficient due to the introduction of the new paradigm and can be implemented easily by using the fundamental external memory primitives. We conduct extensive experiments on real and synthesis graphs and the results demonstrate the efficiency of our proposed algorithm.
Please use this identifier to cite or link to this item: