{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:50:32Z","timestamp":1780822232653,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642114083","type":"print"},{"value":"9783642114090","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_16","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"178-189","source":"Crossref","is-referenced-by-count":3,"title":["An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees"],"prefix":"10.1007","author":[{"given":"Torben","family":"Hagerup","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"16_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.R.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River (1993)"},{"key":"16_CR2","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 Mor. P\u0159\u00edrodov\u011bd. Spol. v Brn\u011b\u00a03, 37\u201358 (1926)","journal-title":"Spol. v Brn\u011b"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1137\/070693217","volume":"38","author":"A.L. Buchsbaum","year":"2008","unstructured":"Buchsbaum, A.L., Georgiadis, L., Kaplan, H., Rogers, A., Tarjan, R.E., Westbrook, J.R.: Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput.\u00a038, 1533\u20131573 (2008)","journal-title":"SIAM J. Comput."},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B.: Computing on a free tree via complexity-preserving mappings. Algorithmica\u00a02, 337\u2013361 (1987)","journal-title":"Algorithmica"},{"key":"16_CR5","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. Assoc. Comput. Mach.\u00a047, 1028\u20131047 (2000)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1142\/S0218195991000049","volume":"1","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B., Rosenberg, B.: The complexity of computing partial sums off-line. Internat. J. Comput. Geometry Appl.\u00a01, 33\u201345 (1991)","journal-title":"Internat. J. Comput. Geometry Appl."},{"key":"16_CR7","unstructured":"Chiang, Y., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 139\u2013149 (1995)"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput.\u00a021, 1184\u20131192 (1992)","journal-title":"SIAM J. Comput."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. System Sci.\u00a048, 533\u2013551 (1994)","journal-title":"J. Comput. System Sci."},{"key":"16_CR10","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. Annals Hist. Comput.\u00a07, 43\u201357 (1985)","journal-title":"Annals Hist. Comput."},{"key":"16_CR11","doi-asserted-by":"crossref","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 randomized linear-time algorithm to find minimum spanning trees. J. Assoc. Comput. Mach.\u00a042, 321\u2013328 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/978-3-540-39658-1_61","volume-title":"Algorithms - ESA 2003","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Sanders, P., Tr\u00e4ff, J.L.: A practical minimum spanning tree algorithm using the cycle property. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 679\u2013690. Springer, Heidelberg (2003)"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02526037","volume":"18","author":"V. King","year":"1997","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica\u00a018, 263\u2013270 (1997)","journal-title":"Algorithmica"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02579443","volume":"5","author":"J. Koml\u00f3s","year":"1985","unstructured":"Koml\u00f3s, J.: Linear verification for spanning trees. Combinatorica\u00a05, 57\u201365 (1985)","journal-title":"Combinatorica"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.cosrev.2008.10.002","volume":"2","author":"M. Mare\u0161","year":"2008","unstructured":"Mare\u0161, M.: The saga of minimum spanning trees. Comput. Sci. Rev.\u00a02, 165\u2013221 (2008)","journal-title":"Comput. Sci. Rev."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00493-006-0014-1","volume":"26","author":"S. Pettie","year":"2006","unstructured":"Pettie, S.: An inverse-Ackermann type lower bound for online minimum spanning tree verification. Combinatorica\u00a026, 207\u2013230 (2006)","journal-title":"Combinatorica"},{"key":"16_CR17","doi-asserted-by":"crossref","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. Assoc. Comput. Mach.\u00a049, 16\u201334 (2002)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1328911.1328916","volume":"4","author":"S. Pettie","year":"2008","unstructured":"Pettie, S., Ramachandran, V.: Randomized minimum spanning tree algorithms using exponentially fewer random bits. ACM Trans. Algorithms\u00a04(1), 5:1\u20135:27 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"16_CR19","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J. Assoc. Comput. Mach.\u00a026, 690\u2013715 (1979)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Space-time tradeoff for answering range queries. In: Proc. 14th Annual ACM Symposium on Theory of Computing (STOC), pp. 128\u2013136 (1982)","DOI":"10.1145\/800070.802185"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:19Z","timestamp":1606185619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}