Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.dis.uniroma1.it/~algo02/esa02/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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