{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T03:22:23Z","timestamp":1761708143608},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677154"},{"type":"electronic","value":"9783540450221"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_6","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:57:25Z","timestamp":1194998245000},"page":"49-60","source":"Crossref","is-referenced-by-count":11,"title":["An Optimal Minimum Spanning Tree Algorithm"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"6_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. Spencer. The Probabilistic Method. Wiley, New York, 1992."},{"key":"6_CR2","first-page":"37","volume":"3","author":"O. Bor\u00fcvka","year":"1926","unstructured":"O. Bor\u00fcvka. O jist\u00e9m probl\u00e9mu minima\u00e1ln\u00edm. Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 3, pp. 37\u201358, 1926. (In Czech).","journal-title":"Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle. A faster deterministic algorithm for minimum spanning trees. In FOCS\u2019 97, pp. 22\u201331, 1997.","DOI":"10.1109\/SFCS.1997.646089"},{"key":"6_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/3-540-68530-8_3","volume-title":"ESA\u2019 98(Venice)","author":"B. Chazelle","year":"1998","unstructured":"B. Chazelle. Car-pooling as a data structuring device: The soft heap. In ESA\u2019 98(Venice), pp. 35\u201342, LNCS 1461, Springer, 1998."},{"key":"6_CR5","unstructured":"B. Chazelle. A minimum spanning tree algorithm with inverse-Ackermann type complexity. NECI Technical Report 99-099, 1999."},{"key":"6_CR6","unstructured":"K. W. Chong, Y. Han and T. W. Lam. On the parallel time complexity of undirected connectivity and minimum spanning trees. In Proc. SODA, pp. 225\u2013234, 1999."},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connexion with graphs. In Numer. Math., 1, pp. 269\u2013271, 1959.","journal-title":"Numer. Math."},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"B. Dixon, M. Rauch, R. E. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Jour. Comput., vol 21, pp. 1184\u20131192, 1992.","journal-title":"SIAM Jour. Comput."},{"key":"6_CR9","first-page":"343","volume":"38","author":"P. Erd\u00f6s","year":"1961","unstructured":"P. Erd\u00f6s, A. R\u00e9nyi On the evolution of random graphs. Bull. Inst. Internat. Statist. 38, pp. 343\u2013347, 1961.","journal-title":"Bull. Inst. Internat. Statist"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman, R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. In JACM 34, pp. 596\u2013615, 1987.","journal-title":"JACM"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"M. Fredman, D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In Proc. FOCS\u2019 90, pp. 719\u2013725, 1990.","DOI":"10.1109\/FSCS.1990.89594"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. N. Gabow","year":"1986","unstructured":"H. N. Gabow, Z. Galil, T. Spencer, R. E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. In Combinatorica 6, pp. 109\u2013122, 1986.","journal-title":"Combinatorica"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R. L. Graham","year":"1985","unstructured":"R. L. Graham, P. Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing 7, pp. 43\u201357, 1985.","journal-title":"Annals of the History of Computing"},{"key":"6_CR14","first-page":"57","volume":"6","author":"V. Jarn\u00edk","year":"1930","unstructured":"V. Jarn\u00edk. O jist\u00e9m probl\u00e9mu minima\u00e1ln\u00edm. Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti 6, pp. 57\u201363, 1930. (In Czech).","journal-title":"Moravsk\u00e9 P\u0159\u00edrodov\u011bdeck\u00e9 Spole\u010dnosti"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D. R. Karger","year":"1995","unstructured":"D. R. Karger, P. N. Klein, and R. E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. JACM, 42:321\u2013328, 1995.","journal-title":"JACM"},{"issue":"4","key":"6_CR16","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0196-6774(80)90017-6","volume":"1","author":"R. M. Karp","year":"1980","unstructured":"R. M. Karp, R. E. Tarjan. Linear expected-time algorithms for connectivity problems. J. Algorithms 1 (1980), no. 4, pp. 374\u2013393.","journal-title":"J. Algorithms"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(90)90084-B","volume":"36","author":"L. L. Larmore","year":"1990","unstructured":"L. L. Larmore. An optimal algorithm with unknown time complexity for convex matrix searching. IPL, vol. 36, pp. 147\u2013151, 1990.","journal-title":"IPL"},{"key":"6_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/978-3-540-48413-4_24","volume-title":"Proc. RANDOM\u2019 99","author":"S. Pettie","year":"1999","unstructured":"S. Pettie, V. Ramachandran. A randomized time-work optimal parallel algorithm for finding a minimum spanning forest Proc. RANDOM\u2019 99, LNCS 1671, Springer, pp. 233\u2013244, 1999."},{"key":"6_CR19","unstructured":"S. Pettie, V. Ramachandran. An optimal minimum spanning tree algorithm. Tech Report TR99-17, Univ. of Texas at Austin, 1999."},{"key":"6_CR20","unstructured":"S. Pettie. Finding minimum spanning trees in O(m\u03b1(m, n)) time. Tech Report TR99-23, Univ. of Texas at Austin, 1999."},{"key":"6_CR21","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R. C. Prim","year":"1957","unstructured":"R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389\u20131401, 1957.","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"6_CR22","first-page":"110","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. In JCSS, 18(2), pp 110\u2013127, 1979.","journal-title":"JCSS"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T08:44:23Z","timestamp":1551084263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}