  We present a work-efficient parallel level-synchronous Breadth First Search
(BFS) algorithm for shared-memory architectures which achieves the theoretical
lower bound on parallel running time. The optimality holds regardless of the
shape of the graph. We also demonstrate the implication of this optimality for
the energy consumption of the program empirically. The key idea is never to use
more processing cores than necessary to complete the work in any computation
step efficiently. We keep the rest of the cores idle to save energy and to
reduce other resource contentions (e.g., bandwidth, shared caches, etc). Our
BFS does not use locks and atomic instructions and is easily extendible to
shared-memory coprocessors.
