Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy 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:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     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.