SpringerLink - Book Chapter

External-Memory Breadth-First Search with Sublinear I/O

Book Series

Lecture Notes in Computer Science

Publisher

Springer Berlin / Heidelberg

ISSN

0302-9743 (Print) 1611-3349 (Online)

Volume

Volume 2461/2002

Book

Algorithms — ESA 2002

DOI

10.1007/3-540-45749-6

2002

ISBN

978-3-540-44180-9

DOI

10.1007/3-540-45749-6_63

Pages

21-26

Subject Collection

Computer Science

SpringerLink Date

Tuesday, January 01, 2002

External-Memory Breadth-First Search with Sublinear I/O

Kurt Mehlhorn⁶ and Ulrich Meyer⁶

(6)	Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany

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 $\Theta \left( {n + \tfrac{{n + m}} {{D \cdot B}} \cdot \log _{M/B} \tfrac{{n + m}} {B}} \right)$ 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 a new approach which requires only $\mathcal{O}(\sqrt {\tfrac{{n \cdot (n + m)}} {{D \cdot B}} + } \tfrac{{n + m}} {{D \cdot B}} \cdot \log _{M/B} \tfrac{{n + m}} {B})$ I/Os. Hence, for $\Omega \sqrt {D \cdot B}$ and all realistic values of $m = \mathcal{O}(n)$ , it improves upon the I/O-performance of the best previous algorithm by a factor $\log _{M/B} \tfrac{{n + m}} {B})$ . Our approach is fairly simple and we conjecture it to be practical. We also give improved algorithms for undirected single-source shortest-paths with small integer edge weights and for semi-external BFS on directed Eulerian graphs.

Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT) and the DFG grant SA 933/1-1.

External-Memory Breadth-First Search with Sublinear I/O

Fulltext Preview (Small, Large)