並列幅優先探索 - level-synchronized BFS

Graph500 のリファレンスコードに使用されている BFS の並列化アルゴリズム。以下、Cray 及び BlueGene/L のアーキテクチャに向けた改良アルゴリズムの提案。

Desigining Multhreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2, David Bader

A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, Andy Yoo

Parallel Boost Library

http://www.boost.org/doc/libs/1_41_0/libs/graph_parallel/doc/html/breadth_first_search.html