Geodesic
On External-Memory Planar Depth First Search
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Data Structures, WADS 2001 , Tome 7 (2003) no. 2, pp. 105-129.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open. For example, no space- and I/O-efficient algorithms are known for depth-first search or breath-first search in sparse graphs. In this paper, we present two new results on I/O-efficient depth-first search in an important class of sparse graphs, namely undirected embedded planar graphs. We develop a new depth-first search algorithm that uses O(sort(N)log(N/M)) I/Os, and show how planar depth-first search can be reduced to planar breadth-first search in O(sort(N)) I/Os. As part of the first result, we develop the first I/O-efficient algorithm for finding a simple cycle separator of an embedded biconnected planar graph. This algorithm uses O(sort(N)) I/Os. 
@article{JGAA_2003_7_2_a1,
     author = {Lars Arge and Ulrich Meyer and Laura Toma and Norbert Zeh},
     title = {On {External-Memory} {Planar} {Depth} {First} {Search}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {105--129},
     publisher = {mathdoc},
     volume = {7},
     number = {2},
     year = {2003},
     doi = {10.7155/jgaa.00063},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00063/}
}
TY  - JOUR
AU  - Lars Arge
AU  - Ulrich Meyer
AU  - Laura Toma
AU  - Norbert Zeh
TI  - On External-Memory Planar Depth First Search
JO  - Journal of Graph Algorithms and Applications
PY  - 2003
SP  - 105
EP  - 129
VL  - 7
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00063/
DO  - 10.7155/jgaa.00063
LA  - en
ID  - JGAA_2003_7_2_a1
ER  - 
%0 Journal Article
%A Lars Arge
%A Ulrich Meyer
%A Laura Toma
%A Norbert Zeh
%T On External-Memory Planar Depth First Search
%J Journal of Graph Algorithms and Applications
%D 2003
%P 105-129
%V 7
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00063/
%R 10.7155/jgaa.00063
%G en
%F JGAA_2003_7_2_a1
Lars Arge; Ulrich Meyer; Laura Toma; Norbert Zeh. On External-Memory Planar Depth First Search. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Data Structures, WADS 2001
					, Tome 7 (2003) no. 2, pp. 105-129. doi : 10.7155/jgaa.00063. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00063/

Cité par Sources :