MPI-INF D1 Publications: Proceedings Article: External-Memory Breadth-First Search with Sublinear I/O

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

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

Action:

Options:

Goto entry point

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:


(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)/(DB) ) 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

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