Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00082
I/O-Optimal Algorithms for Outerplanar Graphs
Vol. 8, no. 1, pp. 47-87, 2004. Regular paper.
Abstract We present linear-I/O algorithms for fundamental graph problems on
embedded outerplanar graphs. We show that
breadth-first search, depth-first search, single-source shortest
paths, triangulation, and computing an ϵ-separator of
size O(1/ϵ) take O(scan(N)) I/Os on embedded
outerplanar graphs. We also show that it takes O(sort(N)) I/Os
to test whether a given graph is outerplanar and to compute an
outerplanar embedding of an outerplanar graph, thereby providing
O(sort(N))-I/O algorithms for the above problems if no
embedding of the graph is given. As all these problems have
linear-time algorithms in internal memory, a simple simulation
technique can be used to improve the I/O-complexity of our
algorithms from O(sort(N)) to O(perm(N)). We prove matching
lower bounds for embedding, breadth-first search, depth-first
search, and single-source shortest paths if no embedding is given.
Our algorithms for the above problems use
a simple linear-I/O time-forward processing algorithm for
rooted trees whose vertices are stored in preorder.
|
Journal Supporters
|