44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03) I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs Cambridge, Massachusettes October 11-October 14 ISBN: 0-7695-2040-5
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.
Citation:
Lars Arge, Norbert Zeh, "I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs," focs, pp.261, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb