MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mehlhorn, Kurt
Meyer, Ulrich		dblp
dblp
Editor(s):
Möhring, Rolf
Raman, Rajeev		dblp
dblp
Not MPII Editor(s):
Möhring, Rolf
Raman, Rajeev
BibTeX cite key*:
MehMey2002
Title, Booktitle
Title*:
External-Memory Breadth-First Search with Sublinear I/O
Booktitle*:
Algorithms - ESA 2002 : 10th Annual European Symposium
Event, URLs
Conference URL::
http://www.dis.uniroma1.it/~algo02/esa02/
Downloading URL:
http://link.springer.de/link/service/series/0558/papers/2461/24610723.pdf
Event Address*:
Rome, Italy
Language:
English
Event Date*
(no longer used):
-- September, 17 - September, 21
Organization:
European Association for Theoretical Computer Science
Event Start Date:
17 September 2002
Event End Date:
21 September 2002
Publisher
Name*:
Springer
URL:
http://www.springer.de
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2461
Number:
Month:
September
Pages:
723-735
Year*:
2002
VG Wort Pages:
22
ISBN/ISSN:
3-540-44180-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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.
URL for the Abstract:
http://link.springer.de/link/service/series/0558/bibs/2461/24610723.htm
Keywords:
External Memory, Graph Algorithms
HyperLinks / References / URLs:
http://dblp.uni-trier.de/db/conf/esa/esa2002.html#MehlhornM02
Download
Access Level:
Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{MehMey2002,
AUTHOR = {Mehlhorn, Kurt and Meyer, Ulrich},
 EDITOR = {M{\"o}hring, Rolf and Raman, Rajeev},
 TITLE = {External-Memory Breadth-First Search with Sublinear {I/O}},
 BOOKTITLE = {Algorithms - ESA 2002 : 10th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2002},
 ORGANIZATION = {European Association for Theoretical Computer Science},
 VOLUME = {2461},
 PAGES = {723--735},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Rome, Italy},
 MONTH = {September},
 ISBN = {3-540-44180-8},
}

Entry last modified by Anja Becker, 03/02/2010
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
09/23/2002 04:32:48 PM
Revisions
10.
9.
8.
7.
6.		Editor(s)
Anja Becker
Christine Kiesel
Tamara Hausmann
Ulrich Meyer
Ulrich Meyer		Edit Dates
07.01.2008 09:54:07
03.10.2006 20:44:29
20.06.2006 11:34:37
03/30/2005 02:22:21 PM
08.09.2003 16:51:42