{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T00:24:59Z","timestamp":1753921499432},"publisher-location":"Berlin\/Heidelberg","reference-count":13,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540543430"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028279","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T05:52:14Z","timestamp":1132638734000},"page":"400-411","source":"Crossref","is-referenced-by-count":22,"title":["An empirical analysis of algorithms for constructing a minimum spanning tree"],"prefix":"10.1007","author":[{"given":"Bernard M. E.","family":"Moret","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry D.","family":"Shapiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"Cheriton, D., and R.E. Tarjan, \u201cFinding minimum spanning trees,\u201d SIAM J. Comput.\n5 (1976), pp. 724\u2013742.","journal-title":"SIAM J. Comput."},{"key":"36_CR2","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"11","author":"J.R. Driscoll","year":"1988","unstructured":"Driscoll, J.R., H.N. Gabow, R. Shrairman, and R.E. Tarjan, \u201cRelaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation,\u201d Comm. ACM\n11 (1988), pp. 1343\u20131354.","journal-title":"Comm. ACM"},{"key":"36_CR3","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M.L. Fredman","year":"1986","unstructured":"Fredman, M.L., R. Sedgewick, D.D. Sleator, and R.E. Tarjan, \u201cThe pairing heap: a new form of self-adjusting heap,\u201d Algorithmica\n1 (1986), pp. 111\u2013129.","journal-title":"Algorithmica"},{"key":"36_CR4","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., and R.E. Tarjan, \u201cFibonacci heaps and their use in improved network optimization algorithms,\u201d Proc. 25th Ann. IEEE Symp. Foundations Comput. Sci. FOCS-84, pp. 338\u2013346; also in final form in J. ACM\n34 (1987), pp. 596\u2013615.","journal-title":"J. ACM"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., and D.E. Willard, \u201cTrans-dichotomous algorithms for minimum spanning trees and shortest paths,\u201d Proc. 31st Ann. IEEE Symp. Foundations Comput. Sci. FOCS-90, pp. 719\u2013725.","DOI":"10.1109\/FSCS.1990.89594"},{"key":"36_CR6","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"Gabow, H.N., Z. Galil, T.H. Spencer, and R.E. Tarjan, \u201cEfficient algorithms for minimum spanning trees on directed and undirected graphs,\u201d Combinatorica\n6 (1986), pp. 109\u2013122.","journal-title":"Combinatorica"},{"key":"36_CR7","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"G. R.L","year":"1985","unstructured":"Graham, R.L., and O. Hell, \u201cOn the history of the minimum spanning tree problem,\u201d Ann. Hist. Comput.\n7 (1985), pp. 43\u201357.","journal-title":"Ann. Hist. Comput."},{"key":"36_CR8","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/5684.5686","volume":"29","author":"D.W. Jones","year":"1986","unstructured":"Jones, D.W. \u201cAn empirical comparison of priority-queue and event-set implementations,\u201d Commun. ACM\n29 (1986), pp. 300\u2013311.","journal-title":"Commun. ACM"},{"key":"36_CR9","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(75)90001-0","volume":"4","author":"D.B. Johnson","year":"1975","unstructured":"Johnson, D.B., \u201cPriority queues with update and finding minimum spanning trees,\u201d Inf. Process. Lett.\n4 (1975), pp. 53\u201357.","journal-title":"Inf. Process. Lett."},{"key":"36_CR10","volume-title":"Algorithms from P to NP. Volume I: Design and Efficiency","author":"B.M.E. Moret","year":"1991","unstructured":"Moret, B.M.E., and H.D. Shapiro. Algorithms from P to NP. Volume I: Design and Efficiency. Benjamin-Cummings, Menlo Park, CA, 1991."},{"key":"36_CR11","unstructured":"Sleator, D.D., and R.E. Tarjan, \u201cSelf-adjusting binary trees,\u201d Proc. 15th Ann. ACM Symp. Theory Comput. STOC-83, pp. 235\u2013245; also in final form in J. ACM\n32 (1985), pp. 652\u2013686."},{"key":"36_CR12","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1145\/214748.214759","volume":"30","author":"J.T. Stasko","year":"1987","unstructured":"Stasko, J.T., and J.S. Vitter, \u201cPairing heaps: experiments and analysis,\u201d Commun. ACM\n30 (1987), pp. 234\u2013249.","journal-title":"Commun. ACM"},{"key":"36_CR13","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E. Data Structures and Network Algorithms. SIAM, Philadelphia, 1983."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028279.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:58:43Z","timestamp":1607551123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0028279","relation":{},"subject":[]}}