{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:19:07Z","timestamp":1725664747946},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_150","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:22Z","timestamp":1330292242000},"page":"416-427","source":"Crossref","is-referenced-by-count":4,"title":["Priority queues on parallel machines"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1007\/3-540-60220-8_70","volume-title":"Proc. 4th Workshop on Algorithms and Data Structures (WADS)","author":"G. S. Brodal","year":"1995","unstructured":"Gerth St\u00f8lting Brodal. Fast meldable priority queues. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 282\u2013290. Springer Verlag, Berlin, 1995."},{"key":"36_CR2","unstructured":"Gerth St\u00f8lting Brodal. Worst-case efficient priority queues. In Proc. 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 52\u201358, 1996."},{"key":"36_CR3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/3-540-58325-4_191","volume-title":"Algorithms and Computation: 5th International Symposium, ISAAC '93","author":"D. Z. Chen","year":"1994","unstructured":"Danny Z. Chen and Xiaobo Hu. Fast and efficient operations on parallel priority queues (preliminary version). In Algorithms and Computation: 5th International Symposium, ISAAC '93, volume 834 of Lecture Notes in Computer Science, pages 279\u2013287. Springer Verlag, Berlin, 1994."},{"key":"36_CR4","first-page":"140","volume-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT)","author":"P. F. Dietz","year":"1992","unstructured":"Paul F. Dietz. Heap construction in the parallel comparison tree model. In Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT), volume 621 of Lecture Notes in Computer Science, pages 140\u2013150. Springer Verlag, Berlin, 1992."},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Paul F. Dietz and Rajeev Raman. Very fast optimal parallel algorithms for heap construction. In Proc. 6th Symposium on Parallel and Distributed Processing, pages 514\u2013521, 1994.","DOI":"10.1109\/SPDP.1994.346128"},{"issue":"11","key":"36_CR6","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J. R. Driscoll","year":"1988","unstructured":"James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343\u20131354, 1988.","journal-title":"Communications of the ACM"},{"issue":"12","key":"36_CR7","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R. W. Floyd","year":"1964","unstructured":"Robert W. Floyd. Algorithm 245: Treesort3. Communications of the ACM, 7(12):701, 1964.","journal-title":"Communications of the ACM"},{"key":"36_CR8","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M. L. Fredman","year":"1986","unstructured":"Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1:111\u2013129, 1986.","journal-title":"Algorithmica"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. In Proc. 25rd Ann. Symp. on Foundations of Computer Science (FOCS), pages 338\u2013346, 1984.","DOI":"10.1109\/SFCS.1984.715934"},{"key":"36_CR10","unstructured":"Joseph J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"36_CR11","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0020-0190(93)90139-Z","volume":"48","author":"C. M. Khoong","year":"1993","unstructured":"C. M. Khoong. Optimal parallel construction of heaps. Information Processing Letters, 48:159\u2013161, 1993.","journal-title":"Information Processing Letters"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Kurt Mehlhorn and Athanasios K. Tsakalidis. Data structures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. MIT Press\/Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50011-4"},{"key":"36_CR14","unstructured":"Maria Cristina Pinotti, Sajal K. Das, and Vincenzo A. Crupi. Parallel and distributed meldable priority queues based on binomial heaps. In Int. Conference on Parallel Processing, 1996."},{"key":"36_CR15","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0020-0190(05)80007-9","volume":"40","author":"M. C. Pinotti","year":"1991","unstructured":"Maria Cristina Pinotti and Geppino Pucci. Parallel priority queues. Information Processing Letters, 40:33\u201340, 1991.","journal-title":"Information Processing Letters"},{"key":"36_CR16","first-page":"130","volume-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT)","author":"M. C. Pinotti","year":"1992","unstructured":"Maria Cristina Pinotti and Geppino Pucci. Parallel algorithms for priority queue operations. In Proc. 3rd Scandinavian Workshop on Algorithm Theory (SWAT), volume 621 of Lecture Notes in Computer Science, pages 130\u2013139. Springer Verlag, Berlin, 1992."},{"key":"36_CR17","doi-asserted-by":"crossref","unstructured":"A. Ranade, S. Cheng, E. Deprit, J. Jones, and S. Shih. Parallelism and locality in priority queues. In Proc. 6th Symposium on Parallel and Distributed Processing, pages 490\u2013496, 1994.","DOI":"10.1109\/SPDP.1994.346131"},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0020-0190(91)90154-A","volume":"37","author":"N. S. V. Rao","year":"1991","unstructured":"Nageswara S. V. Rao and Weixiong Zhang. Building heaps in parallel. Information Processing Letters, 37:355\u2013358, 1991.","journal-title":"Information Processing Letters"},{"issue":"4","key":"36_CR19","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"Jean Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 21(4):309\u2013315, 1978.","journal-title":"Communications of the ACM"},{"issue":"6","key":"36_CR20","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347\u2013348, 1964.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_150.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T10:34:55Z","timestamp":1640946895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_150"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_150","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}