Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 518173.0, MPI für Informatik / Algorithms and Complexity Group
On External-Memory Planar Depth First Search
Authors:Arge, Lars; Meyer, Ulrich; Toma, Laura; Zeh, Norbert
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2001
Title of Proceedings:Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS-01)
Start Page:471
End Page:482
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Providence, Rhode Island, USA
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-BB7C6499549D2339C1256A69004A68B5-...
URL:http://link.springer.de/link/service/series/0558/p...
ISBN:3-540-42423-7
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.