{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:20:41Z","timestamp":1759796441219,"version":"build-2065373602"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T00:00:00Z","timestamp":1755648000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T00:00:00Z","timestamp":1755648000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00453-025-01332-w","type":"journal-article","created":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T09:08:16Z","timestamp":1755680896000},"page":"1899-1932","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Log-Diameter MST Verification and Sensitivity in MPC"],"prefix":"10.1007","volume":"87","author":[{"given":"Sam","family":"Coy","sequence":"first","affiliation":[]},{"given":"Artur","family":"Czumaj","sequence":"additional","affiliation":[]},{"given":"Gopinath","family":"Mishra","sequence":"additional","affiliation":[]},{"given":"Anish","family":"Mukherjee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,20]]},"reference":[{"key":"1332_CR1","doi-asserted-by":"crossref","unstructured":"Andoni, A., Song, Z., Stein, C., Wang, Z., Zhong, P.: Parallel graph connectivity in log diameter rounds. In: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 674\u2013685. IEEE Computer Society, (2018)","DOI":"10.1109\/FOCS.2018.00070"},{"key":"1332_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Stein, C., Song, Z., Wang, Z., Zhong, P.: Parallel graph connectivity in log diameter rounds. CoRR, arXiv:1805.03055, (2018)","DOI":"10.1109\/FOCS.2018.00070"},{"key":"1332_CR3","unstructured":"Andoni A., Stein, C., Zhong, P.: Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 14:1\u201314:16. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, (2019)"},{"key":"1332_CR4","doi-asserted-by":"crossref","unstructured":"Balliu, A., Latypov, R., Maus, Y., Olivetti, D., Uitto, J.: Optimal deterministic massively parallel connectivity on forests. In: Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2589\u20132631. SIAM, (2023)","DOI":"10.1137\/1.9781611977554.ch99"},{"key":"1332_CR5","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Dhulipala, L., Esfandiari, H., \u0141\u0105cki, J., Mirrokni, V.: Near-optimal massively parallel graph connectivity. In: Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1615\u20131636. IEEE Computer Society, (2019)","DOI":"10.1109\/FOCS.2019.00095"},{"issue":"6","key":"1332_CR6","doi-asserted-by":"publisher","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. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"1332_CR7","doi-asserted-by":"crossref","unstructured":"Cole, R., Klein, P.N., Tarjan, R.E.: Finding minimum spanning forests in logarithmic time and linear work using random sampling. In Guy\u00a0E. Blelloch, editor, Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 243\u2013250. ACM, (1996)","DOI":"10.1145\/237502.237563"},{"issue":"5","key":"1332_CR8","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1137\/22M1520177","volume":"52","author":"S Coy","year":"2023","unstructured":"Coy, S., Czumaj, A.: Deterministic massively parallel connectivity. SIAM J. Comput. 52(5), 1269\u20131318 (2023)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1332_CR9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: MapReduce: Simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"issue":"6","key":"1332_CR10","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. 21(6), 1184\u20131192 (1992)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1332_CR11","doi-asserted-by":"publisher","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"},{"key":"1332_CR12","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the MapReduce framework. In: Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), pages 374\u2013383, (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"issue":"1","key":"1332_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"RL Graham","year":"1985","unstructured":"Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. IEEE Ann. Hist. Comput. 7(1), 43\u201357 (1985)","journal-title":"IEEE Ann. Hist. Comput."},{"key":"1332_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, C., Latypov, R., Maus, Y., Pai, S., S\u00e4rkk\u00e4, S., Studen\u00fd, J., Suomela, J., Uitto, J., Vahidi, H.: Fast dynamic programming in trees in the MPC model. In: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM Press, (2023)","DOI":"10.1145\/3558481.3591098"},{"key":"1332_CR15","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Nowicki, K.: MST in $$O(1)$$ rounds of congested clique. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620\u20132632. SIAM, Philadelphia, PA, (2018)","DOI":"10.1137\/1.9781611975031.167"},{"issue":"2","key":"1332_CR16","doi-asserted-by":"publisher","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"},{"key":"1332_CR17","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938\u2013948. SIAM, (2010)","DOI":"10.1137\/1.9781611973075.76"},{"issue":"2","key":"1332_CR18","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 18(2), 263\u2013270 (1997)","journal-title":"Algorithmica"},{"issue":"3","key":"1332_CR19","doi-asserted-by":"publisher","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":"1332_CR20","doi-asserted-by":"crossref","unstructured":"Koml\u00f3s, J.: Linear verification for spanning trees. In: Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS), pages 201\u2013206. IEEE Computer Society, (1984)","DOI":"10.1109\/SFCS.1984.715916"},{"key":"1332_CR21","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: A method for solving graph problems in MapReduce. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 85\u201394, (2011)","DOI":"10.1145\/1989493.1989505"},{"key":"1332_CR22","doi-asserted-by":"crossref","unstructured":"Nowicki, K.: A deterministic algorithm for the MST problem in constant rounds of congested clique. In: Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1154\u20131165, (2021)","DOI":"10.1145\/3406325.3451136"},{"key":"1332_CR23","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), volume 3827 of Lecture Notes in Computer Science, pages 964\u2013973. Springer, (2005)","DOI":"10.1007\/11602613_96"},{"key":"1332_CR24","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. Journal of Graph Algorithms and Applications, 19(1):375\u2013391, 2015. A preliminary version appeared in Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), pp. 964\u2013073, (2005), and in CoRR abs\/1407.1910, arXiv:1407.1910","DOI":"10.7155\/jgaa.00365"},{"issue":"1","key":"1332_CR25","doi-asserted-by":"publisher","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. JACM 49(1), 16\u201334 (2002)","journal-title":"JACM"},{"key":"1332_CR26","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E., Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters, 14(1), 30\u201333 (1982). See Corrigendum. IPL 23(4), 219","DOI":"10.1016\/0020-0190(82)90137-5"},{"key":"1332_CR27","volume-title":"Hadoop: The Definitive Guide","author":"T White","year":"2012","unstructured":"White, T.: Hadoop: The Definitive Guide. O\u2019Reilly Media Inc, US (2012)"},{"key":"1332_CR28","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: Cluster computing with working sets. In: Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), (2010)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01332-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01332-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01332-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:08:08Z","timestamp":1759738088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01332-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,20]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1332"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01332-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,8,20]]},"assertion":[{"value":"19 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}