Abstract

This paper presents I/O-efficientalgorithms for topologically sorting a directed acyclic graph and for the moregeneral problem identifying and topologically sorting the strongly connectedcomponents of a directed graph G = (V , E ). Both algorithms are randomized andhave 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 amachine with size- B blocks and size-M cache/internal memory. These are thefirst algorithms for these problems that do not incur at least one I/O pervertex, and as such these are the first I/O-efficient algorithms for sparsegraphs. By applying the technique of time-forward processing, these algorithmsalso imply I/O-efficient algorithms for most problems on directed acyclicgraphs, such as shortest paths, as well as the single-source reachabilityproblem on arbitrary directed graphs.

Time

4月16日（周二）14:00-15:00

Speaker

Nairen Cao is aPh.D. student from Georgetown University, supervised by Adam O’Neil. His mainresearch focuses on Cryptography(security about RSA-OAEP and selective openingsecurity) and classical algorithm( graph problem, including graph shortcut,topological sort on external memory).

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号