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:
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 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: