{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T22:10:03Z","timestamp":1740262203457,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_20","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"223-235","source":"Crossref","is-referenced-by-count":2,"title":["Melding Priority Queues"],"prefix":"10.1007","author":[{"given":"Ran","family":"Mendelson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. Technical Report DIKU 98-8, Dept. Comput. Sc., Univ. Copenhagen (The result needed from here is not included in the FOCS 1998 extended abstract) (1998)","DOI":"10.7146\/brics.v5i16.21956"},{"key":"20_CR2","unstructured":"Brodal, G.S.: Worst-case efficient priority queues. In: Proc. of 7th SODA, pp. 52\u201358 (1996)"},{"key":"20_CR3","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. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"20_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Standards\u00a071B, 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"20_CR5","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"},{"issue":"3","key":"20_CR6","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information-theoretic bound with fusion trees. Journal of Computer and System Sciences\u00a047(3), 424\u2013436 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences\u00a048, 533\u2013551 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"Gabow, H.N., Galil, Z., Spencer, T.H., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica\u00a06, 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Han, Y.: Deterministic sorting in O(n log log n) time and linear space. In: Proc. of 34th STOC, pp. 602\u2013608 (2002)","DOI":"10.1145\/509989.509993"},{"key":"20_CR10","unstructured":"Han, Y., Thorup, M.: Integer sorting in O(n $\\sqrt{log log n}$ ) expected time and linear space. In: Proc. of 43rd FOCS, pp.135\u2013144 (2002)"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and boolean union-find. In: Proc. of 34th STOC, pp. 573\u2013582 (2002)","DOI":"10.1145\/509989.509990"},{"key":"20_CR12","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Union-find with deletions. In: Proc. of 13th SODA, pp. 19\u201328 (2002)"},{"issue":"4","key":"20_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters\u00a035(4), 183\u2013189 (1990)","journal-title":"Information Processing Letters"},{"key":"20_CR14","unstructured":"Mendelson, R., Thorup, M., Zwick, U.: Meldable RAM priority queues and minimum directed spanning trees. In: Proc. of 15th SODA, pp. 40\u201348 (2004)"},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal\u00a036, 1389\u20131401 (1957)","journal-title":"Bell System Technical Journal"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. Journal of the ACM\u00a022, 215\u2013225 (1975)","journal-title":"Journal of the ACM"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM Journal on Algenraic and Discrete Methods\u00a06, 306\u2013318 (1985)","journal-title":"SIAM Journal on Algenraic and Discrete Methods"},{"issue":"1","key":"20_CR18","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/S0097539795288246","volume":"30","author":"M. Thorup","year":"2000","unstructured":"Thorup, M.: On RAM priority queues. SIAM Journal on Computing\u00a030(1), 86\u2013109 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Equivalence between priority queues and sorting. In: Proc. of 43rd FOCS, pp. 125\u2013134 (2002)","DOI":"10.1109\/SFCS.2002.1181889"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. In: Proc. of 35th STOC, pp. 149\u2013158 (2003)","DOI":"10.1145\/780542.780566"},{"key":"20_CR21","unstructured":"Thorup, M.: On AC0 implementations of fusion trees and atomic heaps. In: Proc. of 14th SODA, pp. 699\u2013707 (2003)"},{"issue":"3","key":"20_CR22","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P.E. Boas van","year":"1977","unstructured":"van Boas, P.E.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06(3), 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"key":"20_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:51:42Z","timestamp":1740261102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}