I/O-Efficient Algorithms for Topological Sort and Related Problems (Nairen Cao)


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(E) = O(E log (E/B)) is the I/O cost B M/B 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.


2019-04-16   14:00 ~ 15:00   


Nairen Cao, Georgetown University


Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics