Abstract
We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights. Our results removes the performance gap between the currently best cache-aware algorithms for these problems and their cache-oblivious counterparts. Our shortest-path algorithm relies on a new data structure, called bucket heap, which is the first cache-oblivious priority queue to efficiently support a weak DecreaseKey operation.
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
Abello, J., Buchsbaum, A.L., Westbrook, J.R.: A functional approach to external graph algorithms. Algorithmica 32(3), 437–458 (2002)
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Communications of the ACM 31(9), 1116–1127 (1988)
Arge, L.: External memory data structures. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 1–29. Springer, Heidelberg (2001)
Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: Cache-oblivious priority queue and graph algorithm applications. In: Proc. 34th STOC, pp. 268–276. ACM, New York (2002)
Arge, L., Brodal, G., Toma, L.: On external-memory MST, SSSP and multiway planar graph separation. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 433–447. Springer, Heidelberg (2000)
Brodal, G.S., Fagerberg, R.: In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 426–438. Springer, Heidelberg (2002)
Brodal, G.S., Fagerberg, R.: Funnel heap - a cache oblivious priority queue. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 219–228. Springer, Heidelberg (2002)
Brodal, G.S., Fagerberg, R.: On the limits of cache-obliviousness. In: Proc. 35th Symposium on Theory of Computing, pp. 307–315. ACM Press, New York (2003)
Brodal, G.S., Fagerberg, R., Meyer, U., Zeh, N.: Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. Technical Report BRICS-RS-04-2, BRICS, Dept. of C. S., University of Aarhus (January 2004)
Buchsbaum, A., Goldwasser, M., Venkatasubramanian, S., Westbrook, J.: On external memory graph traversal. In: Proc. 11th SODA, pp. 859–860. ACM, New York (2000)
Chiang, Y., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 139–149. ACM, New York (1995)
Chowdhury, R.A., Ramachandran, V.: Cache-oblivious shortest paths in graphs using buffer heap. In: Proc. 16th SPAA, ACM-SIAM (2004) (to appear)
Demaine, E.D.: Cache-oblivious data structures and algorithms. In: Proc. EFF summer school on massive data sets. LNCS, Springer, Heidelberg (2004) (to appear)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Num. Math. 1, 269–271 (1959)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 596–615 (1987)
Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: 40th FOCS, pp. 285–297. IEEE, Los Alamitos (1999)
Kumar, V., Schwabe, E.J.: Improved algorithms and data structures for solving graph problems in external memory. In: Proc. 8th SPDP, pp. 169–177. IEEE, Los Alamitos (1996)
Mehlhorn, K., Meyer, U.: External-memory breadth-first search with sublinear I/O. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 723–735. Springer, Heidelberg (2002)
Meyer, U., Sanders, P., Sibeyn, J.F. (eds.): Algorithms for Memory Hierarchies. LNCS, vol. 2625. Springer, Heidelberg (2003)
Meyer, U., Zeh, N.: I/O-efficient undirected shortest paths. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 434–445. Springer, Heidelberg (2003)
Munagala, K., Ranade, A.: I/O-complexity of graph algorithms. In: Proc. 10th Annual Symposium on Discrete Algorithms, pp. 687–694. ACM-SIAM (1999)
Vitter, J.S.: External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys 33(2), 209–271 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brodal, G.S., Fagerberg, R., Meyer, U., Zeh, N. (2004). Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. In: Hagerup, T., Katajainen, J. (eds) Algorithm Theory - SWAT 2004. SWAT 2004. Lecture Notes in Computer Science, vol 3111. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27810-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-27810-8_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22339-9
Online ISBN: 978-3-540-27810-8
eBook Packages: Springer Book Archive