| 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 |
|
Advanced
