| Abstract |
|
We present the first I/O-efficient algorithms for the following fundamental problems on directed planar graphs: finding the strongly connected components, finding a simple-path 23-separator, and computing a depth-first spanning (DFS) tree. Our algorithms for the first two problems perform O(sort(N)) I/Os, where N = V + E and sort(N) = THgr;((N/B)log M/B(N/B)) is the number of I/Os required to sort N elements. The DFS-algorithm performs O(sort(N) log(N/M)) I/Os, where M is the number of elements that fit into main memory.
|
 Additional Information
|
Citation:
Lars Arge, Norbert Zeh,
"I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs,"
focs,
p. 261,
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),
2003
|
