{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:57:00Z","timestamp":1725559020437},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_41","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"480-492","source":"Crossref","is-referenced-by-count":20,"title":["Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norbert","family":"Zeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"41_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","volume":"32","author":"J. Abello","year":"2002","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.R.: A functional approach to external graph algorithms. Algorithmica\u00a032(3), 437\u2013458 (2002)","journal-title":"Algorithmica"},{"issue":"9","key":"41_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Communications of the ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Communications of the ACM"},{"key":"41_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44676-1_1","volume-title":"Algorithms - ESA 2001","author":"L. Arge","year":"2001","unstructured":"Arge, L.: External memory data structures. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 1\u201329. Springer, Heidelberg (2001)"},{"key":"41_CR4","first-page":"268","volume-title":"Proc. 34th STOC","author":"L. Arge","year":"2002","unstructured":"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\u2013276. ACM, New York (2002)"},{"key":"41_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-44985-X_37","volume-title":"Algorithm Theory - SWAT 2000","author":"L. Arge","year":"2000","unstructured":"Arge, L., Brodal, G., Toma, L.: On external-memory MST, SSSP and multiway planar graph separation. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 433\u2013447. Springer, Heidelberg (2000)"},{"key":"41_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-45465-9_37","volume-title":"Automata, Languages and Programming","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 426\u2013438. Springer, Heidelberg (2002)"},{"key":"41_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/3-540-36136-7_20","volume-title":"Algorithms and Computation","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Funnel heap - a cache oblivious priority queue. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 219\u2013228. Springer, Heidelberg (2002)"},{"key":"41_CR8","first-page":"307","volume-title":"Proc. 35th Symposium on Theory of Computing","author":"G.S. Brodal","year":"2003","unstructured":"Brodal, G.S., Fagerberg, R.: On the limits of cache-obliviousness. In: Proc. 35th Symposium on Theory of Computing, pp. 307\u2013315. ACM Press, New York (2003)"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.7146\/brics.v11i2.21827"},{"key":"41_CR10","first-page":"859","volume-title":"Proc. 11th SODA","author":"A. Buchsbaum","year":"2000","unstructured":"Buchsbaum, A., Goldwasser, M., Venkatasubramanian, S., Westbrook, J.: On external memory graph traversal. In: Proc. 11th SODA, pp. 859\u2013860. ACM, New York (2000)"},{"key":"41_CR11","first-page":"139","volume-title":"Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Y. Chiang","year":"1995","unstructured":"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\u2013149. ACM, New York (1995)"},{"key":"41_CR12","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious shortest paths in graphs using buffer heap. In: Proc. 16th SPAA, ACM-SIAM (2004) (to appear)","DOI":"10.1145\/1007912.1007949"},{"key":"41_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. EFF summer school on massive data sets","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D.: Cache-oblivious data structures and algorithms. In: Proc. EFF summer school on massive data sets. LNCS, Springer, Heidelberg (2004) (to appear)"},{"key":"41_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Num. Math.\u00a01, 269\u2013271 (1959)","journal-title":"Num. Math."},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM\u00a034, 596\u2013615 (1987)","journal-title":"Journal of the ACM"},{"key":"41_CR16","first-page":"285","volume-title":"40th FOCS","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: 40th FOCS, pp. 285\u2013297. IEEE, Los Alamitos (1999)"},{"key":"41_CR17","first-page":"169","volume-title":"Proc. 8th SPDP","author":"V. Kumar","year":"1996","unstructured":"Kumar, V., Schwabe, E.J.: Improved algorithms and data structures for solving graph problems in external memory. In: Proc. 8th SPDP, pp. 169\u2013177. IEEE, Los Alamitos (1996)"},{"key":"41_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/3-540-45749-6_63","volume-title":"Algorithms - ESA 2002","author":"K. Mehlhorn","year":"2002","unstructured":"Mehlhorn, K., Meyer, U.: External-memory breadth-first search with sublinear I\/O. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 723\u2013735. Springer, Heidelberg (2002)"},{"key":"41_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms for Memory Hierarchies","year":"2003","unstructured":"Meyer, U., Sanders, P., Sibeyn, J.F. (eds.): Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625. Springer, Heidelberg (2003)"},{"key":"41_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-540-39658-1_40","volume-title":"Algorithms - ESA 2003","author":"U. Meyer","year":"2003","unstructured":"Meyer, U., Zeh, N.: I\/O-efficient undirected shortest paths. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 434\u2013445. Springer, Heidelberg (2003)"},{"key":"41_CR21","unstructured":"Munagala, K., Ranade, A.: I\/O-complexity of graph algorithms. In: Proc. 10th Annual Symposium on Discrete Algorithms, pp. 687\u2013694. ACM-SIAM (1999)"},{"issue":"2","key":"41_CR22","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys\u00a033(2), 209\u2013271 (2001)","journal-title":"ACM Computing Surveys"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:45Z","timestamp":1605759705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}