{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T18:06:02Z","timestamp":1649095562084},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,18]],"date-time":"2014-10-18T00:00:00Z","timestamp":1413590400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s10589-014-9702-8","type":"journal-article","created":{"date-parts":[[2014,10,17]],"date-time":"2014-10-17T10:43:39Z","timestamp":1413542619000},"page":"189-204","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A new algorithm for the minimum spanning tree verification problem"],"prefix":"10.1007","volume":"61","author":[{"given":"Matthew","family":"Williamson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,18]]},"reference":[{"key":"9702_CR1","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF01187017","volume":"11","author":"H Booth","year":"1992","unstructured":"Booth, H., Westbrook, J.: A linear algorithm for analysis of minimum spanning and shortest path trees of planar graphs. Algorithmica 11, 341\u2013352 (1992)","journal-title":"Algorithmica"},{"key":"9702_CR2","unstructured":"Bor\u016fvka, O.: Bor\u016fvka. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Moravsk\u00e9 Pr\u0306trodov\u0115deck\u00e9 Spolec\u0306nosti v Brn\u0115 3, 37\u201358 (1926)"},{"key":"9702_CR3","unstructured":"Bright, W.: D Programming Language, 2001. http:\/\/www.dlang.org"},{"key":"9702_CR4","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: Linear-time pointer-machine algorithms for least common ancestors, mst verification, and dominators. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC\u201998, pp. 279\u2013288. ACM: New York, NY (1998)","DOI":"10.1145\/276698.276764"},{"key":"9702_CR5","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"9702_CR6","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.: 9th DIMACS implementation challenge-Shortest Paths (2005). http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"issue":"6","key":"9702_CR7","doi-asserted-by":"crossref","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. 21(6), 1184\u20131192 (1992)","journal-title":"SIAM J. Comput."},{"key":"9702_CR8","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: An even simpler linear-time algorithm for verifying minimum spanning trees. In WG, pp. 178\u2013189 (2009)","DOI":"10.1007\/978-3-642-11409-0_16"},{"key":"9702_CR9","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16, 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"issue":"2","key":"9702_CR10","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321\u2013328 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"9702_CR11","doi-asserted-by":"crossref","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 18(2), 263\u2013270 (1997)","journal-title":"Algorithmica"},{"key":"9702_CR12","doi-asserted-by":"crossref","unstructured":"Komlos, J.: Linear verification for spanning trees. In SFCS\u201984: Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 201\u2013206. IEEE Computer Society: Washington, DC (1984)","DOI":"10.1109\/SFCS.1984.715916"},{"key":"9702_CR13","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. In: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, PODC\u201906, pp. 26\u201334. ACM: New York, NY (2006)","DOI":"10.1145\/1146381.1146389"},{"issue":"2","key":"9702_CR14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.jda.2009.03.001","volume":"8","author":"JB Orlin","year":"2010","unstructured":"Orlin, J.B., Madduri, K., Subramani, K., Williamson, M.: A faster algorthm for the single source shortest path problems with few distinct postive lengths. J. Discret. Algorithm 8(2), 189\u2013198 (2010)","journal-title":"J. Discret. Algorithm"},{"issue":"2","key":"9702_CR15","doi-asserted-by":"crossref","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 26(2), 207\u2013230 (2006)","journal-title":"Combinatorica"},{"key":"9702_CR16","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. Technical report, Stanford (1975)"},{"key":"9702_CR17","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22, 215\u2013225 (1975)","journal-title":"J. ACM"},{"issue":"4","key":"9702_CR18","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"Robert Endre Tarjan","year":"1979","unstructured":"Tarjan, Robert Endre: Applications of path compression on balanced trees. J. ACM 26(4), 690\u2013715 (1979)","journal-title":"J. ACM"},{"issue":"1","key":"9702_CR19","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"RE Tarjan","year":"1982","unstructured":"Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett. 14(1), 30\u201333 (1982)","journal-title":"Inf. Process. Lett."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-014-9702-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-014-9702-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-014-9702-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T05:07:27Z","timestamp":1565932047000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-014-9702-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,18]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9702"],"URL":"https:\/\/doi.org\/10.1007\/s10589-014-9702-8","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,18]]}}}