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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Abello, A. Buchsbaum, and J. Westbrook. A functional approach to external graph algorithms. Algorithmica, 32(3):437–458, 2002.
A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, 1988.
L. Arge, G. Brodal, and L. Toma. On external-memory MST, SSSP and multi-way planar graph separation. In Proc. 8th Scand. Workshop on Algorithmic Theory, volume 1851 of LNCS, pages 433–447. Springer, 2000.
L. Arge, U. Meyer, L. Toma, and N. Zeh. On external-memory planar depth first search. In Proc. 7th Intern. Workshop on Algorithms and Data Structures (WADS 2001), volume 2125 of LNCS, pages 471–482. Springer, 2001.
L. Arge, L. Toma, and J. S. Vitter. I/O-efficient algorithms for problems on gridbased terrains. In Proc. Workshop on Algorithm Engeneering and Experiments (ALENEX), 2000.
M. Atallah and U. Vishkin. Finding Euler tours in parallel. Journal of Computer and System Sciences, 29(30):330–337, 1984.
A. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, and J. Westbrook. On external memory graph traversal. In Proc. 11th Symp. on Discrete Algorithms, pages 859–860. ACM-SIAM, 2000.
Y.-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamasia, D.E. Vengroff, and J. S. Vitter. External memory graph algorithms. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 139–149, 1995.
V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proc. 8th Symp. on Parallel and Distrib. Processing, pages 169–177. IEEE, 1996.
A. Maheshwari and N. Zeh. External memory algorithms for outerplanar graphs. In Proc. 10th Intern. Symp. on Algorithms and Computations, volume 1741 of LNCS, pages 307–316. Springer, 1999.
A. Maheshwari and N. Zeh. I/O-efficient algorithms for graphs of bounded treewidth. In Proc. 12th Ann. Symp. on Discrete Algorithms, pages 89–90. ACM-SIAM, 2001.
A. Maheshwari and N. Zeh. I/O-optimal algorithms for planar graphs using separators. In Proc. 13th Ann. Symp. on Discrete Algorithms, pages 372–381. ACM-SIAM, 2002.
U. Meyer. External memory BFS on undirected graphs with bounded degree. In Proc. 12th Ann. Symp. on Discrete Algorithms, pages 87–88. ACM-SIAM, 2001.
K. Munagala and A. Ranade. I/O-complexity of graph algorithms. In Proc. 10th Symp. on Discrete Algorithms, pages 687–694. ACM-SIAM, 1999.
M.H. Nodine and J. S. Vitter. Greed sort: An optimal sorting algorithm for multiple disks. Journal of the ACM, 42(4):919–933, 1995.
J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two level memories. Algorithmica, 12(2–3):110–147, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mehlhorn, K., Meyer, U. (2002). External-Memory Breadth-First Search with Sublinear I/O. In: Möhring, R., Raman, R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45749-6_63
Download citation
DOI: https://doi.org/10.1007/3-540-45749-6_63
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44180-9
Online ISBN: 978-3-540-45749-7
eBook Packages: Springer Book Archive