{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:12:42Z","timestamp":1740287562637,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642140303"},{"type":"electronic","value":"9783642140310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14031-0_51","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T09:50:06Z","timestamp":1277718606000},"page":"479-488","source":"Crossref","is-referenced-by-count":1,"title":["The Violation Heap: A Relaxed Fibonacci-Like Heap"],"prefix":"10.1007","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"51_CR1","first-page":"263","volume":"146","author":"G. Adelson-Velskii","year":"1962","unstructured":"Adelson-Velskii, G., Landis, E.: On an information organization algorithm. Doklady Akademia Nauk SSSR\u00a0146, 263\u2013266 (1962)","journal-title":"Doklady Akademia Nauk SSSR"},{"key":"51_CR2","unstructured":"Brodal, G.S.: Worst-case efficient priority queues. In: Proceedings of the 7th ACM-SIAM symp. on Disc. Algorithms, pp. 52\u201358 (1996)"},{"key":"51_CR3","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)","edition":"2"},{"key":"51_CR4","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J. Driscoll","year":"1988","unstructured":"Driscoll, J., Gabow, H., Shrairman, R., Tarjan, R.E.: Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. ACM Comm.\u00a031, 1343\u20131354 (1988)","journal-title":"ACM Comm."},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Elmasry, A.: Pairing heaps with O(loglogn) decrease cost. In: Proceedings of the 20th ACM-SIAM symp. on Disc. Algorithms, pp. 471\u2013476 (2009)","DOI":"10.1137\/1.9781611973068.52"},{"key":"51_CR6","unstructured":"Elmasry, A.: Violation heaps: an alternative to Fibonacci heaps. CoRR abs\/0812.2851 (2008)"},{"key":"51_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/978-3-540-27810-8_19","volume-title":"Algorithm Theory - SWAT 2004","author":"A. Elmasry","year":"2004","unstructured":"Elmasry, A.: Layered heaps. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 212\u2013222. Springer, Heidelberg (2004)"},{"key":"51_CR8","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00236-008-0070-7","volume":"45","author":"A. Elmasry","year":"2008","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Two-tier relaxed heaps. Acta Informatica\u00a045, 193\u2013210 (2008)","journal-title":"Acta Informatica"},{"issue":"4","key":"51_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":"51_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":"51_CR11","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, 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"51_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/978-3-642-04128-0_59","volume-title":"Algorithms - ESA 2009","author":"B. Haeupler","year":"2009","unstructured":"Haeupler, B., Sen, S., Tarjan, R.E.: Rank-Pairing Heaps. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 659\u2013670. Springer, Heidelberg (2009)"},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P.: A general technique for implementation of efficient priority queues. In: Proceedings of the 3rd Israel Symp. on the Theory of Computing Systems, pp. 57\u201366 (1995)","DOI":"10.1109\/ISTCS.1995.377045"},{"key":"51_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-44985-X_5","volume-title":"Algorithm Theory - SWAT 2000","author":"J. Iacono","year":"2000","unstructured":"Iacono, J.: Improved upper bounds for pairing heaps. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 32\u201345. Springer, Heidelberg (2000)"},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Tarjan, R.E.: Thin heaps, thick heaps. ACM Trans. on Algorithms, Article 3 4(1) (2008)","DOI":"10.1145\/1328911.1328914"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and boolean union-find. In: Proceedings of the ACM Symp. on Theory of Computing, pp. 573\u2013582 (2002)","DOI":"10.1145\/509907.509990"},{"key":"51_CR17","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1090\/dimacs\/015\/09","volume":"15","author":"B. Moret","year":"1994","unstructured":"Moret, B., Shapiro, H.: An empirical assessment of algorithms for constructing a minimum spanning tree. DIMACS Monographs in Disc. Math. and Theoretical Comp. Science\u00a015, 99\u2013117 (1994)","journal-title":"DIMACS Monographs in Disc. Math. and Theoretical Comp. Science"},{"key":"51_CR18","unstructured":"Peterson, G.: A balanced tree scheme for meldable heaps with updates. Technical Report GIT-ICS-87-23, School of Information and Comp. Science, Georgia Institute of Technology (1987)"},{"key":"51_CR19","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Towards a final analysis of pairing heaps. In: Proceedings of the 46th IEEE Symp. on Foundations of Comp. Science, pp. 174\u2013183 (2005)","DOI":"10.1109\/SFCS.2005.75"},{"issue":"3","key":"51_CR20","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM\u00a032(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"51_CR21","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1145\/214748.214759","volume":"30","author":"J. Stasko","year":"1987","unstructured":"Stasko, J., Vitter, J.S.: Pairing heaps: experiments and analysis. ACM Comm.\u00a030(3), 234\u2013249 (1987)","journal-title":"ACM Comm."},{"issue":"1","key":"51_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0166-218X(02)00219-6","volume":"126","author":"T. Takaoka","year":"2003","unstructured":"Takaoka, T.: Theory of 2-3 heaps. Disc. Appl. Math.\u00a0126(1), 115\u2013128 (2003)","journal-title":"Disc. Appl. Math."},{"key":"51_CR23","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. ACM Comm.\u00a021, 309\u2013314 (1978)","journal-title":"ACM Comm."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14031-0_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T08:45:18Z","timestamp":1740213918000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14031-0_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642140303","9783642140310"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14031-0_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}