DocumentCode :
2169697
Title :
I/O-efficient strong connectivity and depth-first search for directed planar graphs
Author :
Arge, Lars ; Zeh, Norbert
Author_Institution :
Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
fYear :
2003
fDate :
11-14 Oct. 2003
Firstpage :
261
Lastpage :
270
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 2/3-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) = Θ((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.
Keywords :
computational complexity; directed graphs; tree data structures; tree searching; DFS tree; I/O-efficient algorithm; I/O-efficient strong connectivity; depth-first search; depth-first spanning; directed planar graph; Computer science; Electronic switching systems; Engineering profession; Fellows; Geographic Information Systems; Performance evaluation; Runtime; Sorting; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2040-5
Type :
conf
DOI :
10.1109/SFCS.2003.1238200
Filename :
1238200
Link To Document :
بازگشت