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

Mehlhorn, Kurt; Meyer, Ulrich; Möhring, Rolf; Raman, Rajeev

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

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

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45038

Meyer, Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45250

Raman, Rajeev
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Mehlhorn, K., & Meyer, U. (2002). External-Memory Breadth-First Search with Sublinear I/O. In Algorithms - ESA 2002: 10th Annual European Symposium (pp. 723-735). Berlin, Germany: Springer.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-2F7A-6

要旨

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.