{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:46:36Z","timestamp":1743014796541,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":19,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_239","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:35:29Z","timestamp":1214505329000},"page":"541-544","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Spanning Trees"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"239_CR1_239","first-page":"37","volume":"3","author":"O. Bor\u016fvka","year":"1926","unstructured":"Bor\u016fvka, O.: O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 3, 37\u201358 (1926). In Czech","journal-title":"Pr\u00e1ce Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti"},{"issue":"6","key":"239_CR2_239","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: A\u00a0minimum spanning tree algorithm with inverse\u2010Ackermann type complexity. J. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"239_CR3_239","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, TH., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)","edition":"2"},{"key":"239_CR4_239","unstructured":"Eppstein, D.: Geometry in action: minimum spanning trees. http:\/\/www.ics.uci.edu\/~eppstein\/gina\/mst.html"},{"key":"239_CR5_239","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 6, 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"239_CR6_239","volume-title":"Computers and intractability: a guide to NP\u2010completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a\u00a0guide to NP\u2010completeness. Freeman, San Francisco (1979)"},{"issue":"1","key":"239_CR7_239","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7(1), 43\u201357 (1985)","journal-title":"Ann. Hist. Comput."},{"key":"239_CR8_239","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/11815921_19","volume-title":"Proc. 11th Workshop Structural, Syntactic, and Statistical Pattern Recognition (SSPR). LNCS, vol. 4109","author":"A. Ion","year":"2006","unstructured":"Ion, A., Kropatsch, W.G., Haxhimusa, Y.: Considerations regarding the minimum spanning tree pyramid segmentation method. In: Proc. 11th Workshop Structural, Syntactic, and Statistical Pattern Recognition (SSPR). LNCS, vol. 4109, pp.\u00a0182\u2013190. Springer, Berlin (2006)"},{"key":"239_CR9_239","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A\u00a0randomized linear-time algorithm for finding minimum spanning trees. J. ACM 42, 321\u2013329 (1995)","journal-title":"J. ACM"},{"key":"239_CR10_239","first-page":"679","volume-title":"Proc. 11th Annual European Symposium on Algorithms. LNCS, vol. 2832","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Sanders, P., Tr\u00e4ff, J.L.: A\u00a0practical minimum spanning tree algorithm using the cycle property. In: Proc.\u00a011th Annual European Symposium on Algorithms. LNCS, vol. 2832, pp.\u00a0679\u2013690. Springer, Berlin (2003)"},{"key":"239_CR11_239","doi-asserted-by":"crossref","unstructured":"Moret, B.M.E., Shapiro, H.D.: An empirical assessment of algorithms for constructing a\u00a0minimum spanning tree. In: DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 15, Am. Math. Soc., Providence, RI (1994)","DOI":"10.1090\/dimacs\/015\/09"},{"key":"239_CR12_239","unstructured":"Pettie, S.: On the shortest path and minimum spanning tree problems. Ph.D. thesis, The University of Texas, Austin, August 2003"},{"key":"239_CR13_239","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Towards a\u00a0final analysis of pairing heaps. In: Proc. 46th Annual Symposium on Foundations of Computer Science (FOCS), 2005, pp.\u00a0174\u2013183","DOI":"10.1109\/SFCS.2005.75"},{"issue":"1","key":"239_CR14_239","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/505241.505243","volume":"49","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16\u201334 (2002)","journal-title":"J. ACM"},{"issue":"6","key":"239_CR15_239","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S. Pettie","year":"2005","unstructured":"Pettie, S., Ramachandran, V.: A\u00a0shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398\u20131431 (2005)","journal-title":"SIAM J. Comput."},{"key":"239_CR16_239","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational geometry. Springer, New York (1985)"},{"issue":"4","key":"239_CR17_239","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/S0010-2180(98)00023-6","volume":"115","author":"S. Subramaniam","year":"1998","unstructured":"Subramaniam, S., Pope, S.B.: A\u00a0mixing model for turbulent reactive flows based on euclidean minimum spanning trees. Combust. Flame 115(4), 487\u2013514 (1998)","journal-title":"Combust. Flame"},{"key":"239_CR18_239","volume-title":"CBMS-NSF Reg. Conf. Ser. Appl. Math., vol. 44","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data structures and network algorithms. In: CBMS-NSF Reg. Conf. Ser. Appl. Math., vol. 44. SIAM, Philadelphia (1983)"},{"issue":"3","key":"239_CR19_239","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single\u2010source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362\u2013394 (1999)","journal-title":"J. ACM"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T21:32:30Z","timestamp":1738272750000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_239"}},"subtitle":["2002; Pettie, Ramachandran"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_239","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}