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: 201793.0, MPI für Informatik / Algorithms and Complexity Group
External-Memory Breadth-First Search with Sublinear I/O
Authors:Mehlhorn, Kurt; Meyer, Ulrich
Editors:Möhring, Rolf; Raman, Rajeev
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:Algorithms - ESA 2002 : 10th Annual European Symposium
Start Page:723
End Page:735
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Rome, Italy
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2002-09-17
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:Breadth-first search (BFS) is a basic graph exploration technique.
We give the first external-memory algorithm for sparse
undirected graphs with sublinear I/O. The best
previous algorithm requires O( n + sort(n+m) ) I/Os
on a graph with n nodes and m edges and a machine with
main-memory of size M, D parallel disks, and block size B.

We present two versions of a new algorithm which requires only
O( sqrt( n/m * (n+m)/(D*B) ) * log_{M/B} (n/B) + sort(n+m)) I/Os
(expected or worst-case, respectively).
Hence, for m = O(n), they improve upon the I/O-performance
of the best previous algorithm by nearly a factor of sqrt(D*B).
Our approach is fairly simple and we conjecture at least the
randomized version to be practical.
Last Change of the Resource (YYYY-MM-DD):2003-09-08
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:ISBN:3-540-44180-8
LOCALID:C1256428004B93B8-A255EBD0F85324E4C1256C3D004FE88A-...
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.