{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T22:15:38Z","timestamp":1761862538001},"publisher-location":"Boston","reference-count":24,"publisher":"Kluwer Academic Publishers","isbn-type":[{"type":"print","value":"1402081405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/1-4020-8141-3_17","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T10:15:11Z","timestamp":1140516911000},"page":"195-208","source":"Crossref","is-referenced-by-count":20,"title":["Engineering an External Memory Minimum Spanning Tree Algorithm"],"prefix":"10.1007","author":[{"given":"Roman","family":"Dementiev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Schultes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jop","family":"Sibeyn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"17_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","volume":"32","author":"J. Abello","year":"2002","unstructured":"J. Abello, A. Buchsbaum, and J. Westbrook. A functional approach to external graph algorithms. Algorithmica, 32(3):437\u2013458, 2002.","journal-title":"Algorithmica"},{"issue":"9","key":"17_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter. The input\/output complexity of sorting and related problems. Communications of the ACM, 31(9): 1116\u20131127, 1988.","journal-title":"Communications of the ACM"},{"doi-asserted-by":"crossref","unstructured":"L. Arge, G. Brodal, and L. Toma. On external memory MST, SSSP and multi-way planar graph separation. In 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of LNCS, pages 433\u2013447. Springer, 2000.","key":"17_CR3","DOI":"10.1007\/3-540-44985-X_37"},{"unstructured":"O. Boruvka. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e0ce, Moravsk\u00e9 Prirodovedeck\u00e9 Spolecnosti, pages 1\u201358, 1926.","key":"17_CR4"},{"doi-asserted-by":"crossref","unstructured":"Gerth St\u00f8lting Brodal and Jyrki Katajainen. Worst-case efficient external-memory priority queues. In 6th Scandinavian Workshop on Algorithm Theory, number 1432 in LNCS, pages 107\u2013118. Springer Verlag, Berlin, 1998.","key":"17_CR5","DOI":"10.1007\/BFb0054359"},{"unstructured":"Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 139\u2013149, 1995.","key":"17_CR6"},{"doi-asserted-by":"crossref","unstructured":"R. Dementiev and P. Sanders. Asynchronous paralleldisk sorting. In 15th ACM Symposium on Parallelism in Algorithms and Architectures, pages 138\u2013148, San Diego, 2003.","key":"17_CR7","DOI":"10.1145\/777432.777435"},{"unstructured":"R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn. Engineering an external memory minimum spanning tree algorithm\u2014full paper. http:\/\/www.mpi-sb.mpg.de\/sanders\/papers\/emstfull.ps.gz , 2004.","key":"17_CR8"},{"key":"17_CR9","first-page":"57","volume":"6","author":"V. Jarn\u00edk","year":"1930","unstructured":"V. Jarn\u00edk. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Moravsk\u00e9 p\u00e9trirodov\u00f0edeck\u2316e Spole\u2316cnosti 6:57\u201363, 1930. In Czech.","journal-title":"Pr\u00e1ce Moravsk\u00e9 p\u00e9trirodov\u00f0edeck\u2316e Spole\u2316cnosti"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D. Karger","year":"1995","unstructured":"D. Karger, P. N. Klein, and R. E. Tarjan. A randomized linear-time algorithm for finding minimum spanning trees. J. Assoc. Comput. Mach., 42:321\u2013329, 1995.","journal-title":"J. Assoc. Comput. Mach."},{"doi-asserted-by":"crossref","unstructured":"I. Katriel, P. Sanders, and J. L. Tr\u00e4ff. A practical minimum spanning tree algorithm using the cycle property. In 11th European Symposium on Algorithms (ESA), number 2832 in LNCS, pages 679\u2013690. Springer, 2003.","key":"17_CR11","DOI":"10.1007\/978-3-540-39658-1_61"},{"unstructured":"D. E. Knuth. The Art of Computer Programming\u2014Seminumerical Algorithms, volume 2. Addison Wesley, 2nd edition, 1981.","key":"17_CR12"},{"unstructured":"K. Mehlhorn and S. N\u00e4her. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.","key":"17_CR13"},{"doi-asserted-by":"crossref","unstructured":"U. Meyer, P. Sanders, and J. Sibeyn, editors. Algorithms for Memory Hierarchies, volume 2625 of LNCS Tutorial. Springer, 2003.","key":"17_CR14","DOI":"10.1007\/3-540-36574-5"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1090\/dimacs\/015\/09","volume":"15","author":"B.M.E. Moret","year":"1994","unstructured":"B.M.E. Moret and H.D. Shapiro. An empirical assessment of algorithms for constructing a minimum spanning tree. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 15:99\u2013117, 1994.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"issue":"1","key":"17_CR16","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/PL00003817","volume":"12","author":"M. Naor","year":"1999","unstructured":"M. Naor and O. Reingold. On the construction of pseudorandom permutations: Luby Rackoff revisited. Journal of Cryptology: the journal of the International Association for Cryptologic Research, 12(1):29\u201366, 1999.","journal-title":"Journal of Cryptology: the journal of the International Association for Cryptologic Research"},{"unstructured":"J. Ne\u0161et\u0159il, H. Milkov\u00e1, and H. Ne\u0161et\u0159ilov\u00e1. Otakar boruvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history. DMATH: Discrete Mathematics, 233, 2001.","key":"17_CR17"},{"doi-asserted-by":"crossref","unstructured":"R. C. Prim. Shortest connection networks and some generalizations. Bell Systems Technical Journal, pages 1389\u20131401, November 1957.","key":"17_CR18","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"issue":"6","key":"17_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0190(98)00127-6","volume":"67","author":"P. Sanders","year":"1998","unstructured":"P. Sanders. Random permutations on distributed, external and hierarchical memory. Information Processing Letters, 67(6):305\u2013310, 1998.","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"P. Sanders. Fast priority queues for cached memory. In ALENEX\u2019 99 Workshop on Algorithm Engineering and Experimentation, number 1619 in LNCS, pages 312\u2013327. Springer, 1999.","key":"17_CR20","DOI":"10.1007\/3-540-48518-X_19"},{"unstructured":"D. Schultes. External memory minimum spanning trees. Bachelor thesis, Max-Planck-Institut f. Informatik and Saarland University, http:\/\/www.dominik-schultes.de\/emmst\/ , August 2003.","key":"17_CR21"},{"doi-asserted-by":"crossref","unstructured":"J. F. Sibeyn. External connected components. In 12th Scandinavian Workshop on Algorithm Theory, Springer LNCS, 2004. to appear.","key":"17_CR22","DOI":"10.1007\/978-3-540-27810-8_40"},{"issue":"3","key":"17_CR23","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362\u2013391, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan. Efficiency of a good but not linear set merging algorithm. Journal of the ACM, 22:215\u2013225, 1975.","journal-title":"Journal of the ACM"}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T16:28:09Z","timestamp":1619540889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["1402081405"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_17","relation":{},"subject":[]}}