Paper Info
Title
I/O-Efficient Algorithms for Topological Sort and Related Problems.
Abstract
This paper presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = (V, E). Both algorithms are randomized and have I/O-costs O(sort(E) · poly(log V)), with high probability, where sort[MATH HERE] is the I/O cost of sorting an |E|-element array on a machine with size-B blocks and size-M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.
Year
DOI
Venue
2019
10.5555/3310435.3310559
SODA '19: Symposium on Discrete Algorithms San Diego California January, 2019
Field
DocType
Citations 
Discrete mathematics,Topological sorting,Computer science,Input/output
Conference
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Nairen Cao100.34
Jeremy T. Fineman258736.10
Katina Russell300.34
Eugene Yang432.11