{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T05:13:45Z","timestamp":1739337225176,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_59","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"659-670","source":"Crossref","is-referenced-by-count":3,"title":["Rank-Pairing Heaps"],"prefix":"10.1007","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[]},{"given":"Siddhartha","family":"Sen","sequence":"additional","affiliation":[]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"59_CR1","unstructured":"Brodal, G.: Worst-case efficient priority queues. In: SODA, pp. 52\u201358 (1996)"},{"key":"59_CR2","doi-asserted-by":"crossref","unstructured":"Brown, M.R.: Implementation and analysis of binomial queue algorithms. SIAM J. Comput., 298\u2013319 (1978)","DOI":"10.1137\/0207026"},{"key":"59_CR3","unstructured":"Chan, T.M.: Quake heaps: a simple alternative to Fibonacci heaps (2009)"},{"key":"59_CR4","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. Numer. Math.\u00a01, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"11","key":"59_CR5","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J.R. Driscoll","year":"1988","unstructured":"Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Comm. ACM\u00a031(11), 1343\u20131354 (1988)","journal-title":"Comm. ACM"},{"key":"59_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Standards B71, 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bur. Standards B"},{"key":"59_CR7","unstructured":"Elmasry, A.: Violation heaps: A better substitute for Fibonacci heaps. CoRR (2008)"},{"key":"59_CR8","doi-asserted-by":"crossref","unstructured":"Elmasry, A.: Pairing heaps with O(loglogn) decrease cost. In: SODA, pp. 471\u2013476 (2009)","DOI":"10.1137\/1.9781611973068.52"},{"issue":"4","key":"59_CR9","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1145\/320211.320214","volume":"46","author":"M.L. Fredman","year":"1999","unstructured":"Fredman, M.L.: On the efficiency of pairing heaps and related data structures. J. ACM\u00a046(4), 473\u2013501 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"59_CR10","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M.L. Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica\u00a01(1), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"key":"59_CR11","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. In: FOCS, pp. 338\u2013346, 24\u201326 (1984)","DOI":"10.1109\/SFCS.1984.715934"},{"issue":"3","key":"59_CR12","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. J. ACM\u00a034(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"2","key":"59_CR13","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(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"59_CR14","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P.: A general technique for implementation of efficient priority queues. In: ISTCS, pp. 57\u201366 (1995)","DOI":"10.1109\/ISTCS.1995.377045"},{"key":"59_CR15","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and boolean union-find. In: STOC, pp. 573\u2013582 (2002)","DOI":"10.1145\/509907.509990"},{"key":"59_CR16","unstructured":"Kaplan, H., Tarjan, R.E.: New heap data structures. Technical Report TR-597-99, Princeton Univ. (1999)"},{"issue":"1","key":"59_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1328911.1328914","volume":"4","author":"H. Kaplan","year":"2008","unstructured":"Kaplan, H., Tarjan, R.E.: Thin heaps, thick heaps. ACM Trans. Alg.\u00a04(1), 1\u201314 (2008)","journal-title":"ACM Trans. Alg."},{"key":"59_CR18","series-title":"Fundamental Algorithms","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. Fundamental Algorithms, vol.\u00a01. Addison-Wesley, Reading (1973)"},{"key":"59_CR19","series-title":"Sorting and Searching","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"key":"59_CR20","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/BF01758771","volume":"7","author":"A.M. Liao","year":"1992","unstructured":"Liao, A.M.: Three priority queue applications revisited. Algorithmica\u00a07, 415\u2013427 (1992)","journal-title":"Algorithmica"},{"key":"59_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/BFb0028279","volume-title":"Algorithms and Data Structures","author":"B. Moret","year":"1991","unstructured":"Moret, B., Shapiro, H.: An empirical analysis of algorithms for constructing a minimum spanning tree. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 400\u2013411. Springer, Heidelberg (1991)"},{"issue":"1","key":"59_CR22","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. J. Disc. Math.\u00a05(1), 54\u201366 (1992)","journal-title":"J. Disc. Math."},{"key":"59_CR23","unstructured":"Peterson, G.L.: A balanced tree scheme for meldable heaps with updates. Technical Report GIT-ICS-87-23, Georgia Inst. of Tech (1987)"},{"key":"59_CR24","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Towards a final analysis of pairing heaps. In: FOCS, pp. 174\u2013183 (2005)","DOI":"10.1109\/SFCS.2005.75"},{"issue":"3","key":"59_CR25","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1145\/214748.214759","volume":"30","author":"J.T. Stasko","year":"1987","unstructured":"Stasko, J.T., Vitter, J.S.: Pairing heaps: experiments and analysis. Comm. ACM\u00a030(3), 234\u2013249 (1987)","journal-title":"Comm. ACM"},{"key":"59_CR26","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. J. Alg. Disc. Methods\u00a06, 306\u2013318 (1985)","journal-title":"J. Alg. Disc. Methods"},{"key":"59_CR27","unstructured":"Various. The Fifth DIMACS Challenge\u2014Priority Queue Tests (1996)"},{"issue":"4","key":"59_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"Vuillemin, J.: A data structure for manipulating priority queues. Comm. ACM\u00a021(4), 309\u2013315 (1978)","journal-title":"Comm. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T04:16:19Z","timestamp":1739333779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}