MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Arge, Lars
Meyer, Ulrich
Toma, Laura
Zeh, Norbert		dblp
dblp
dblp
dblp
Editor(s):
Dehne, Frank
Sack, Jörg-Rüdiger
Tamassia, R.		dblp
dblp
dblp
BibTeX cite key*:
ArMeToZe2001
Title, Booktitle
Title*:
On External-Memory Planar Depth First Search
Booktitle*:
Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS-01)
Event, URLs
Conference URL::
http://www.wads.org/
Downloading URL:
http://link.springer.de/link/service/series/0558/papers/2125/21250471.pdf
Event Address*:
Providence, Rhode Island, USA
Language:
English
Event Date*
(no longer used):
August, 8 - August, 10
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2125
Number:
Month:
August
Pages:
471-482
Year*:
2001
VG Wort Pages:
22
ISBN/ISSN:
3-540-42423-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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 breadth-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 efficient
depth-first search algorithm and show how planar depth-first search
in general can be reduced to planar breadth-first search. As part
of the first result we develop the first I/O-efficient algorithm
for finding a simple cycle separator of a biconnected planar graph.
Together with other recent reducibility results, the second result
provides further evidence that external memory breadth-first search
is among the hardest problems on planar graphs.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{ArMeToZe2001,
AUTHOR = {Arge, Lars and Meyer, Ulrich and Toma, Laura and Zeh, Norbert},
 EDITOR = {Dehne, Frank and Sack, J{\"o}rg-R{\"u}diger and Tamassia, R.},
 TITLE = {On External-Memory Planar Depth First Search},
 BOOKTITLE = {Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS-01)},
 PUBLISHER = {Springer},
 YEAR = {2001},
 VOLUME = {2125},
 PAGES = {471--482},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Providence, Rhode Island, USA},
 MONTH = {August},
 ISBN = {3-540-42423-7},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ulrich Meyer		Created
06/12/2001 15:32:44
Revisions
7.
6.
5.
4.
3.		Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker		Edit Dates
02.05.2007 18:02:09
07/11/2002 10:13:25 AM
04/25/2002 07:48:46 PM
08.04.2002 14:36:59
22.03.2002 13:37:23