{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:46Z","timestamp":1759637806399},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T00:00:00Z","timestamp":1368576000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s00224-013-9479-7","type":"journal-article","created":{"date-parts":[[2013,5,14]],"date-time":"2013-05-14T06:56:14Z","timestamp":1368514574000},"page":"318-340","source":"Crossref","is-referenced-by-count":18,"title":["Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification"],"prefix":"10.1007","volume":"53","author":[{"given":"Liah","family":"Kor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,15]]},"reference":[{"issue":"1\u20132","key":"9479_CR1","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0304-3975(96)00286-1","volume":"186","author":"Y. Afek","year":"1997","unstructured":"Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its applications to self stabilization. Theor. Comput. Sci. 186(1\u20132), 199\u2013230 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9479_CR2","first-page":"230","volume-title":"Proc. 19th ACM Symp. on Theory of Computing (STOC)","author":"B. Awerbuch","year":"1987","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: Proc. 19th ACM Symp. on Theory of Computing (STOC), NY, pp.\u00a0230\u2013240 (1987)"},{"key":"9479_CR3","first-page":"268","volume-title":"Proc. IEEE Symp. on the Foundations of Computer Science","author":"B. Awerbuch","year":"1991","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: Proc. IEEE Symp. on the Foundations of Computer Science, pp.\u00a0268\u2013277 (1991)"},{"issue":"2","key":"9479_CR4","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. J. ACM 37(2), 238\u2013256 (1990)","journal-title":"J. ACM"},{"issue":"4","key":"9479_CR5","doi-asserted-by":"crossref","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. 38(4), 1533\u20131573 (2008)","journal-title":"SIAM J. Comput."},{"key":"9479_CR6","unstructured":"Burns, J.E.: A formal model for message passing systems. Technical report TR-91, Computer Science Dept., Indiana University, Bloomington (1980)"},{"issue":"5","key":"9479_CR7","doi-asserted-by":"crossref","first-page":"1950","DOI":"10.1109\/26.387408","volume":"43","author":"I. Cidon","year":"1995","unstructured":"Cidon, I., Gopal, I., Kaplan, M., Kutten, S.: A distributed control architecture of high-speed networks. IEEE Trans. Commun. 43(5), 1950\u20131960 (1995)","journal-title":"IEEE Trans. Commun."},{"key":"9479_CR8","volume-title":"Proc. 43th ACM Symp. on Theory of Computing (STOC)","author":"A. Das Sarma","year":"2011","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proc. 43th ACM Symp. on Theory of Computing (STOC) (2011)"},{"key":"9479_CR9","volume-title":"Proc. 30th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC)","author":"A. Das Sarma","year":"2011","unstructured":"Das Sarma, A., Nanongkai, D., Pandurangan, G.: A tight unconditional lower bound on distributed random walk computation. In: Proc. 30th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (2011)"},{"issue":"6","key":"9479_CR10","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."},{"issue":"1","key":"9479_CR11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF02523235","volume":"17","author":"B. Dixon","year":"1997","unstructured":"Dixon, B., Tarjan, R.E.: Optimal parallel verification of minimum spanning trees in logarithmic time. Algorithmica 17(1), 11\u201318 (1997)","journal-title":"Algorithmica"},{"issue":"6","key":"9479_CR12","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/s002360050180","volume":"36","author":"S. Dolev","year":"1999","unstructured":"Dolev, S., Gouda, M., Schneider, M.: Requirements for silent stabilization. Acta Inform. 36(6), 447\u2013462 (1999)","journal-title":"Acta Inform."},{"key":"9479_CR13","first-page":"708","volume-title":"FOCS","author":"P. Fraigniaud","year":"2011","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: FOCS, pp.\u00a0708\u2013717 (2011)"},{"key":"9479_CR14","first-page":"371","volume-title":"DISC","author":"P. Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. In: DISC, pp.\u00a0371\u2013385 (2012)"},{"key":"9479_CR15","first-page":"493","volume-title":"Proc. 16th ACM Symp. on Theory of Computing (STOC)","author":"G.N. Frederickson","year":"1984","unstructured":"Frederickson, G.N., Lynch, N.A.: The impact of synchronous communication on the problem of electing a leader in a ring. In: Proc. 16th ACM Symp. on Theory of Computing (STOC), NY, pp.\u00a0493\u2013503 (1984)"},{"key":"9479_CR16","first-page":"719","volume-title":"Proc. 31st IEEE FOCS","author":"M.L. Fredman","year":"1990","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In: Proc. 31st IEEE FOCS, pp.\u00a0719\u2013725 (1990)"},{"issue":"1","key":"9479_CR17","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R.G. Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"9479_CR18","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J. Garay","year":"1998","unstructured":"Garay, J., Kutten, S.A., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9479_CR19","doi-asserted-by":"crossref","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\u201347 (1985)","journal-title":"Ann. Hist. Comput."},{"key":"9479_CR20","first-page":"185","volume-title":"Proc. 17th ACM Symp. on Theory of Computing (STOC)","author":"D. Harel","year":"1985","unstructured":"Harel, D.: A linear time algorithm for finding dominators in flow graphs and related problems. In: Proc. 17th ACM Symp. on Theory of Computing (STOC), pp.\u00a0185\u2013194 (1985)"},{"issue":"2","key":"9479_CR21","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. ACM 42(2), 321\u2013328 (1995)","journal-title":"J. ACM"},{"issue":"1","key":"9479_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M. Katz","year":"2005","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2005)","journal-title":"SIAM J. Comput."},{"key":"9479_CR23","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, 263\u2013270 (1997)","journal-title":"Algorithmica"},{"issue":"3","key":"9479_CR24","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(97)00050-1","volume":"62","author":"V. King","year":"1997","unstructured":"King, V., Poon, C.K., Ramachandran, V., Sinha, S.: An optimal EREW PRAM algorithm for minimum spanning tree verification. Inf. Process. Lett. 62(3), 153\u2013159 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9479_CR25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02579443","volume":"5","author":"J. Koml\u00f6s","year":"1985","unstructured":"Koml\u00f6s, J.: Linear verification for spanning trees. Combinatorica 5, 57\u201365 (1985)","journal-title":"Combinatorica"},{"issue":"4","key":"9479_CR26","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s00446-007-0025-1","volume":"20","author":"A. Korman","year":"2007","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20(4), 253\u2013266 (2007)","journal-title":"Distrib. Comput."},{"issue":"4","key":"9479_CR27","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A. Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"9479_CR28","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge Univ. Press, New York (1997)"},{"issue":"1","key":"9479_CR29","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J.\u00a0Algorithms 28(1), 40\u201366 (1998)","journal-title":"J.\u00a0Algorithms"},{"key":"9479_CR30","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Universal bounds for leader election. Unpublished manuscript (2012)"},{"key":"9479_CR31","first-page":"63","volume-title":"Proc. 20th ACM Symp. on Principles of Distributed Computing (PODC)","author":"Z. Lotker","year":"2001","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed mst for constant diameter graphs. In: Proc. 20th ACM Symp. on Principles of Distributed Computing (PODC), NY, pp.\u00a063\u201371 (2001)"},{"issue":"5","key":"9479_CR32","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D. Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9479_CR33","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. ACM 49(1), 16\u201334 (2002)","journal-title":"J. ACM"},{"key":"9479_CR34","unstructured":"Rubinovich, V.: Distributed minimum spanning tree construction. Master\u2019s thesis, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science (1999)"},{"key":"9479_CR35","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. ACM 26, 690\u2013715 (1979)","journal-title":"J. ACM"},{"key":"9479_CR36","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9479-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9479-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9479-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:25Z","timestamp":1558698865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9479-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,15]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9479"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9479-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,15]]}}}