{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:48:04Z","timestamp":1742914084784,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":19,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_239","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:06Z","timestamp":1461268986000},"page":"1322-1325","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Minimum Spanning Trees"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"217_CR13536","first-page":"37","volume":"3","author":"O Bor\u016fvka","year":"1926","unstructured":"Bor\u016fvka O (1926) O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 3:37\u201358. In Czech","journal-title":"Pr\u00e1ce Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti"},{"issue":"6","key":"217_CR13537","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B Chazelle","year":"2000","unstructured":"Chazelle B (2000) A minimum spanning tree algorithm with inverse-Ackermann type complexity. J ACM 47(6):1028\u20131047","journal-title":"J ACM"},{"key":"217_CR13538","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT, Cambridge"},{"key":"217_CR13539","unstructured":"Eppstein D, Geometry in action: minimum spanning trees. http:\/\/www.ics.uci.edu\/~eppstein\/gina\/mst.html . Last downloaded Nov 2014"},{"key":"217_CR13540","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow HN, Galil Z, Spencer TH, Tarjan RE (1986) Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6:109\u2013122","journal-title":"Combinatorica"},{"key":"217_CR13541","volume-title":"Computers and intractability: a guide to NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to NP-completeness. Freeman, San Francisco"},{"issue":"1","key":"217_CR13542","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"RL Graham","year":"1985","unstructured":"Graham RL, Hell P (1985) On the history of the minimum spanning tree problem. Ann Hist Comput 7(1):43\u201357","journal-title":"Ann Hist Comput"},{"key":"217_CR13543","doi-asserted-by":"crossref","unstructured":"Ion A, Kropatsch WG, Haxhimusa Y (2006) Considerations regarding the minimum spanning tree pyramid segmentation method. In: Proceedings of the 11th workshop structural, syntactic, and statistical pattern recognition (SSPR), Hong Kong. LNCS, vol\u00a04109. Springer, Berlin, pp\u00a0182\u2013190","DOI":"10.1007\/11815921_19"},{"key":"217_CR13544","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger DR, Klein PN, Tarjan RE (1995) A randomized linear-time algorithm for finding minimum spanning trees. J ACM 42:321\u2013329","journal-title":"J ACM"},{"key":"217_CR13545","doi-asserted-by":"crossref","unstructured":"Katriel I, Sanders P, Tr\u00e4ff JL (2003) A practical minimum spanning tree algorithm using the cycle property. In: Proceedings of the 11th annual European symposium on algorithms, Budapest. LNCS, vol\u00a02832. Springer, Berlin, pp\u00a0679\u2013690","DOI":"10.1007\/978-3-540-39658-1_61"},{"key":"217_CR13546","doi-asserted-by":"crossref","unstructured":"Moret BME, Shapiro HD (1994) An empirical assessment of algorithms for constructing a minimum spanning tree. In: Computational support for discrete mathematics. DIMACS series in discrete mathematics and theoretical computer science, vol\u00a015. American Mathematical Society, Providence","DOI":"10.1090\/dimacs\/015\/09"},{"key":"217_CR13547","unstructured":"Pettie S (2003) On the shortest path and minimum spanning tree problems. Ph.D. thesis, The University of Texas, Austin"},{"key":"217_CR13548","doi-asserted-by":"crossref","unstructured":"Pettie S (2005) Towards a final analysis of pairing heaps. In: Proceedings of the 46th annual symposium on foundations of computer science (FOCS), Pittsburgh, pp\u00a0174\u2013183","DOI":"10.1109\/SFCS.2005.75"},{"issue":"1","key":"217_CR13549","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/505241.505243","volume":"49","author":"S Pettie","year":"2002","unstructured":"Pettie S, Ramachandran V (2002) An optimal minimum spanning tree algorithm. J ACM 49(1):16\u201334","journal-title":"J ACM"},{"issue":"6","key":"217_CR13550","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S Pettie","year":"2005","unstructured":"Pettie S, Ramachandran V (2005) A shortest path algorithm for real-weighted undirected graphs. SIAM J Comput 34(6):1398\u20131431","journal-title":"SIAM J Comput"},{"key":"217_CR13551","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry","author":"FP Preparata","year":"1985","unstructured":"Preparata FP, Shamos MI (1985) Computational geometry. Springer, New York"},{"issue":"4","key":"217_CR13552","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 SB (1998) A mixing model for turbulent reactive flows based on euclidean minimum spanning trees. Combust Flame 115(4):487\u2013514","journal-title":"Combust Flame"},{"key":"217_CR13553","volume-title":"Data structures and network algorithms. CBMS-NSF regional conference series in applied mathematics","author":"RE Tarjan","year":"1983","unstructured":"Tarjan RE (1983) Data structures and network algorithms. CBMS-NSF regional conference series in applied mathematics, vol\u00a044. SIAM, Philadelphia"},{"issue":"3","key":"217_CR13554","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M Thorup","year":"1999","unstructured":"Thorup M (1999) Undirected single-source shortest paths with positive integer weights in linear time. J ACM\u00a046(3):362\u2013394","journal-title":"J ACM"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T19:05:45Z","timestamp":1567796745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_239","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}