Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section