loading...
I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs
Cambridge, Massachusettes October 11-October 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.123820044th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Lars Arge, Norbert Zeh, "I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs," Foundations of Computer Science, Annual IEEE Symposium on, pp. 261, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2003.1238200,
author = {Lars Arge and Norbert Zeh},
title = {I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2003},
issn = {0272-5428},
pages = {261},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238200},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs
SN - 0272-5428
SP
EP
A1 - Lars Arge,
A1 - Norbert Zeh,
PY - 2003
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Lars Arge, Duke University
Norbert Zeh, Dalhousie University
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.