{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T06:25:38Z","timestamp":1785219938123,"version":"3.55.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"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":["Distrib. Comput."],"published-print":{"date-parts":[[2023,3]]},"DOI":"10.1007\/s00446-021-00398-3","type":"journal-article","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T06:02:39Z","timestamp":1624946559000},"page":"57-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A distributed algorithm for directed minimum-weight spanning tree"],"prefix":"10.1007","volume":"36","author":[{"given":"Orr","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,29]]},"reference":[{"key":"398_CR1","unstructured":"Becker, R., Karrenbauer, A., Krinninger, S., Lenzen, C.: Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In: 31st International Symposium on Distributed Computing (DISC), pp. 7:1\u20137:16 (2017)"},{"key":"398_CR2","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Nanongkai, D.: Distributed exact weighted all-pairs shortest paths in near-linear time. In Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2019)","DOI":"10.1145\/3313276.3316326"},{"key":"398_CR3","unstructured":"Bock, F.: An algorithm to construct a minimum directed spanning tree in a directed network. In: Developments in Operations Research, pp. 29\u201344 (1971)"},{"key":"398_CR4","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 143\u2013152 (2015)","DOI":"10.1145\/2767386.2767414"},{"key":"398_CR5","doi-asserted-by":"crossref","unstructured":"Chechik, S., Mukhtar, D.: Single-source shortest paths in the CONGEST model with improved bound. In: Symposium on Principles of Distributed Computing (PODC), pp. 464\u2013473. ACM (2020)","DOI":"10.1145\/3382734.3405729"},{"key":"398_CR6","unstructured":"Chechik, S.: Private communication"},{"issue":"1","key":"398_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986)","journal-title":"Inf. Control"},{"key":"398_CR8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)"},{"key":"398_CR9","doi-asserted-by":"crossref","unstructured":"Dory, M.: Distributed approximation of minimum k-edge-connected spanning subgraphs. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 149\u2013158 (2018)","DOI":"10.1145\/3212734.3212760"},{"issue":"4","key":"398_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bureau Stand. 71B(4), 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bureau Stand."},{"key":"398_CR11","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A simple deterministic distributed MST algorithm, with near-optimal time and message complexities. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 157\u2013163 (2017)","DOI":"10.1145\/3087801.3087823"},{"issue":"2","key":"398_CR12","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"398_CR13","doi-asserted-by":"publisher","first-page":"1282","DOI":"10.1016\/j.jcss.2006.07.002","volume":"72","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72(8), 1282\u20131308 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"398_CR14","doi-asserted-by":"crossref","unstructured":"Forster, S., Nanongkai, D.: A faster distributed single-source shortest paths algorithm. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 686\u2013697 (2018)","DOI":"10.1109\/FOCS.2018.00071"},{"key":"398_CR15","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: Proceedings of the Twenty-third Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"issue":"2","key":"398_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow, H.N., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"398_CR17","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. In: Proceedings of IEEE 34th Annual Foundations of Computer Science, pp. 659\u2013668 (1993)"},{"key":"398_CR18","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, mst, and min-cut. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202\u2013219 (2016)","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"398_CR19","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Li, J.: Improved distributed algorithms for exact shortest paths. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 431\u2013444 (2018)","DOI":"10.1145\/3188745.3188948"},{"key":"398_CR20","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Parter, M.: MST in log-star rounds of congested clique. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pp. 19\u201328 (2016)","DOI":"10.1145\/2933057.2933103"},{"key":"398_CR21","unstructured":"Haeupler, B., Li, J.: Faster distributed shortest path approximations via shortcuts. In: 32nd International Symposium on Distributed Computing (DISC), pp. 33:1\u201333:14 (2018)"},{"key":"398_CR22","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Klasing, R., Monien, B., Peine, R.: Dissemination of Information in Interconnection Networks (Broadcasting & Gossiping), pp. 125\u2013212. Springer, USA (1996)","DOI":"10.1007\/978-1-4757-2491-2_5"},{"issue":"6","key":"398_CR23","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1109\/TCOM.1983.1095883","volume":"31","author":"P Humblet","year":"1983","unstructured":"Humblet, P.: A distributed algorithm for minimum weight directed spanning trees. IEEE Trans. Commun. 31(6), 756\u2013762 (1983)","journal-title":"IEEE Trans. Commun."},{"issue":"4","key":"398_CR24","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"398_CR25","doi-asserted-by":"publisher","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. Algorithms 28(1), 40\u201366 (1998)","journal-title":"J. Algorithms"},{"issue":"2","key":"398_CR26","first-page":"1396","volume":"14","author":"TH Liu","year":"1965","unstructured":"Liu, T.H., Chu, Y.J.: On the shortest arborescence of a directed graph. Sci. Sin. 14(2), 1396\u20131400 (1965)","journal-title":"Sci. Sin."},{"issue":"1","key":"398_CR27","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"398_CR28","doi-asserted-by":"crossref","unstructured":"Lovasz, L.: Computing ears and branchings in parallel. In: 26th Annual Symposium on Foundations of Computer Science (FOCS), pp. 464\u2013467 (1985)","DOI":"10.1109\/SFCS.1985.16"},{"key":"398_CR29","first-page":"309","volume":"7","author":"F Maffioli","year":"1979","unstructured":"Maffioli, F., Camerini, P.M., Fratta, L.: A note on finding optimum branchings. Networks 7, 309\u2013312 (1979)","journal-title":"Networks"},{"issue":"2","key":"398_CR30","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1002\/net.3230100202","volume":"10","author":"F Maffioli","year":"1980","unstructured":"Maffioli, F., Camerini, P.M., Fratta, L.: The k best spanning arborescences of a network. Networks 10(2), 91\u2013109 (1980)","journal-title":"Networks"},{"key":"398_CR31","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"398_CR32","doi-asserted-by":"crossref","unstructured":"Nowicki, K., Jurdzinski, T.: MST in O(1) rounds of congested clique. In: Proceedings of the Twenty-Ninth Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 2620\u20132632 (2018)","DOI":"10.1137\/1.9781611975031.167"},{"key":"398_CR33","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: A time- and message-optimal distributed algorithm for minimum spanning trees. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 743\u2013756 (2017)","DOI":"10.1145\/3055399.3055449"},{"issue":"2","key":"398_CR34","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"AA Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"398_CR35","unstructured":"Rubinovich, V., Peleg, D.: A near-tight lower bound on the time complexity of distributed mst construction. In: 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 253\u2013261 (1999)"},{"issue":"5","key":"398_CR36","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"398_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"RE Tarjan","year":"1965","unstructured":"Tarjan, R.E.: Finding optimum branchings. Networks 7(1), 25\u201335 (1965)","journal-title":"Networks"},{"key":"398_CR38","doi-asserted-by":"crossref","unstructured":"Thurimella, R.: Sub-linear distributed algorithms for sparse certificates and biconnected components. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC) (1995)","DOI":"10.1145\/224964.224968"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00398-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00398-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00398-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,4]],"date-time":"2023-03-04T09:04:23Z","timestamp":1677920663000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00398-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,29]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["398"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00398-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,29]]},"assertion":[{"value":"5 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}