{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T20:12:21Z","timestamp":1788898341278,"version":"build-2803163510"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter $\\Diam$. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sublinear in n, but linear in $\\Diam$ (specifically, $O(\\Diam + n^\\varepsilon \\cdot \\log^* n)$ for $\\varepsilon = \\frac{\\ln 3}{\\ln 6} = 0.6131...$). Our result is achieved through the application of graph decomposition and edge-elimination-by-pipelining techniques that may be of independent interest.<\/jats:p>","DOI":"10.1137\/s0097539794261118","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"302-316","source":"Crossref","is-referenced-by-count":118,"title":["A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees"],"prefix":"10.1137","volume":"27","author":[{"given":"Juan A.","family":"Garay","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Ingo Alth\u00f6fer, Gautam Das, David Dobkin, Deborah Joseph, Generating sparse spanners for weighted graphs, Lecture Notes in Comput. Sci., Vol. 447, Springer, Berlin, 1990, 26\u2013371076014","DOI":"10.1007\/3-540-52846-6_75"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch,\n                      Optimal distributed algorithms for minimum\u2010weight spanning tree, counting, leader election and related problems\n                      , in Proc. 19th ACM Symp. on Theory of Computing, ACM, New York, 1987, pp. 230\u2013240.","DOI":"10.1145\/28395.28421"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Goldberg, M. Luby, and S. Plotkin,\n                      Network decomposition and locality in distributed computation\n                      , in Proc. 30th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1989, pp. 364\u2013375.","DOI":"10.1109\/SFCS.1989.63504"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77618"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, S. Kutten, and D. Peleg,\n                      Competitive distributed job load balancing\n                      , Proc. 24th ACM Symp. on Theory of Computing, ACM, New York, 1992, pp. 571\u2013580.","DOI":"10.1145\/129712.129768"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and D. Peleg,\n                      Network synchronization with polylogarithmic overhead\n                      , in 31st IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1990, pp. 514\u2013522.","DOI":"10.1109\/FSCS.1990.89572"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and D. Peleg,\n                      Concurrent online tracking of mobile users\n                      , Proc. ACM SIGCOMM Symposium on Communication, Architectures and Protocols, ACM, New York, 1991, pp. 221\u2013233.","DOI":"10.1145\/115992.116013"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Simonovits, Paul Erdo\u02dds\u2019 influence on extremal graph theory, Algorithms Combin., Vol. 14, Springer, Berlin, 1997, 148\u201319297h:05092","DOI":"10.1007\/978-3-642-60406-5_15"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"F. Chin and H. F. Ting,\n                      An almost linear time and O(nlog(n)+e) messages distributed algorithm for minimum\u2010weight spanning trees\n                      , in Proc. 26th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1985, pp. 257\u2013266.","DOI":"10.1109\/SFCS.1985.7"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"E. Gafni,\n                      Improvements in the time complexity of two message\u2010optimal election algorithms\n                      , in Proc. 4th Symp. on Principles of Distributed Computing, ACM, New York, 1995, pp. 175\u2013185.","DOI":"10.1145\/323596.323612"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Garay, S. Kutten, and D. Peleg,\n                      A sub\u2010linear time distributed algorithm for minimum\u2010weight spanning trees\n                      , in Proc. 34th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 659\u2013668.","DOI":"10.1109\/SFCS.1993.366821"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, S. Plotkin, and G. Shannon,\n                      Parallel symmetry breaking in sparse graphs\n                      , in Proc. 19th ACM Symp. on Theory of Computing, ACM, New York, 1987, pp. 315\u2013324.","DOI":"10.1145\/28395.28429"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"N. Linial,\n                      Distributive graph algorithms\u2014global solutions from local data\n                      , in Proc. 28th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1987, pp. 331\u2013335.","DOI":"10.1109\/SFCS.1987.20"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094721"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90074-Y"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. Panconesi and A. Srinivasan,\n                      Improved distributed algorithms for coloring and network decomposition problems\n                      , in Proc. 24th ACM Symp. on Theory of Computing, ACM, New York, 1992, pp. 581\u2013592.","DOI":"10.1145\/129712.129769"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794261118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:42Z","timestamp":1787336082000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794261118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794261118"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794261118","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}