External Memory BFS on Undirected Graphs with Bounded Degree

Meyer, Ulrich

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

External Memory BFS on Undirected Graphs with Bounded Degree

MPS-Authors

/persons/resource/persons45038

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

External Resource

No external resources are shared

Fulltext (restricted access)

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

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Meyer, U. (2001). External Memory BFS on Undirected Graphs with Bounded Degree. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01) (pp. 87-88). New York, USA: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3190-8

Abstract

We give the first external memory algorithm for breadth-first search (BFS) which achieves $o(n)$ I/Os on arbitrary undirected graphs with $n$ nodes and maximum node degree $d$. Let $M$ and $B>d$ denote the main memory size and block size, respectively. Using $\mathrm{Sort}(x)=\Theta(\frac{x}{B}\cdot \log_{M/B}\frac{x}{B})$, our algorithm needs ${\cal O}(\frac{n}{\gamma \cdot \log_d B} + \mathrm{Sort}(n \cdot B^\gamma))$ I/Os and ${\cal O}(n \cdot B^\gamma)$ external space for an arbitrary parameter $0 <\gamma \le 1/2$. The result carries over to BFS, depth-first search (DFS) and single source shortest paths (SSSP) on undirected planar graphs with arbitrary node degrees.