MPI-INF D1 Publications: Proceedings Article: On External-Memory Planar Depth First Search

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Goto entry point

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

URL of the conference:	http://www.wads.org/
URL for downloading the paper:	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:


(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

Edit History (please click the blue arrow to see the details)

	Editor(s) Ulrich Meyer	Created 06/12/2001 03:32:44 PM
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

Attachment Section