{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:10:36Z","timestamp":1763467836894},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2007,10,30]],"date-time":"2007-10-30T00:00:00Z","timestamp":1193702400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1007\/s00446-007-0047-8","type":"journal-article","created":{"date-parts":[[2007,10,29]],"date-time":"2007-10-29T06:05:31Z","timestamp":1193637931000},"page":"391-402","source":"Crossref","is-referenced-by-count":52,"title":["A fast distributed approximation algorithm for minimum spanning trees"],"prefix":"10.1007","volume":"20","author":[{"given":"Maleq","family":"Khan","sequence":"first","affiliation":[]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,30]]},"reference":[{"key":"47_CR1","doi-asserted-by":"crossref","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, pp. 230\u2013240 (1987)","DOI":"10.1145\/28395.28421"},{"key":"47_CR2","doi-asserted-by":"crossref","unstructured":"Chin, F., Ting, H.: An almost linear time and O(n log n \u00a0+\u00a0 e) messages distributed algorithm for minimum-weight spanning trees. In: Proc. 26th IEEE Symp. Foundations of Computer Science, pp. 257\u2013266 (1985)","DOI":"10.1109\/SFCS.1985.7"},{"key":"47_CR3","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1990","unstructured":"Cormen T., Leiserson C. and Rivest R. (1990). Introduction to Algorithms. MIT Press, Cambridge"},{"key":"47_CR4","unstructured":"Elkin, M.: A faster distributed protocol for constructing minimum spanning tree. In: Proc. of the ACM-SIAM Symp. on Discrete Algorithms, pp. 352\u2013361 (2004)"},{"issue":"4","key":"47_CR5","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin M. (2004). An overview of distributed approximation. ACM SIGACT News Distrib. Comput. Column 35(4): 40\u201357","journal-title":"ACM SIGACT News Distrib. Comput. Column"},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In: Proc. of the ACM Symposium on Theory of Computing, pp. 331\u2013340 (2004)","DOI":"10.1145\/1007352.1007407"},{"key":"47_CR7","doi-asserted-by":"crossref","unstructured":"Gafni, E.: Improvements in the time complexity of two message-optimal election algorithms. In: Proc. of the 4th Symp. on Principles of Distributed Computing, pp. 175\u2013185 (1985)","DOI":"10.1145\/323596.323612"},{"issue":"1","key":"47_CR8","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R. Gallager","year":"1983","unstructured":"Gallager R., Humblet P. and Spira P. (1983). A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1): 66\u201377","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"47_CR9","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J. Garay","year":"1998","unstructured":"Garay J., Kutten S. and Peleg D. (1998). A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27: 302\u2013316","journal-title":"SIAM J. Comput."},{"issue":"6","key":"47_CR10","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1007\/s00224-006-1251-9","volume":"39","author":"M. Herlihy","year":"2006","unstructured":"Herlihy M., Kuhn F., Tirthapura S. and Wattenhofer R. (2006). Dynamic analysis of the arrow distributed protocol. Theory Comput. Syst. 39(6): 875\u2013901","journal-title":"Theory Comput. Syst."},{"key":"47_CR11","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding W. (1963). Probability for sums of bounded random variables. J. Am. Stat. Assoc. 58: 13\u201330","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"47_CR12","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"Imase M. and Waxman B. (1991). Dynamic steiner tree problem. Siam J. Discrete Math. 4(3): 369\u2013384","journal-title":"Siam J. Discrete Math."},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"Khan, M., Pandurangan, G., Kumar, V.: A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms. Theor. Compu. Sci. 385(1\u20133): 101\u2013114","DOI":"10.1016\/j.tcs.2007.05.028"},{"issue":"2","key":"47_CR14","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/0216019","volume":"16","author":"E. Korach","year":"1987","unstructured":"Korach E., Moran S. and Zaks S. (1987). The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Comput. 16(2): 231\u2013236","journal-title":"SIAM J. Comput."},{"key":"47_CR15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0304-3975(89)90103-5","volume":"64","author":"E. Korach","year":"1989","unstructured":"Korach E., Moran S. and Zaks S. (1989). Optimal lower bounds for some distributed algorithms for a complete network of processors. Theor. Comput. Sci. 64: 125\u2013132","journal-title":"Theor. Comput. Sci."},{"key":"47_CR16","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten S. and Peleg D. (1998). Fast distributed construction of k-dominating sets and applications. J. Algorithms 28: 40\u201366","journal-title":"J. Algorithms"},{"issue":"1","key":"47_CR17","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z. Lotker","year":"2005","unstructured":"Lotker Z., Patt-Shamir B., Pavlov E. and Peleg D. (2005). Minimum-weight spanning tree construction in O(log\u00a0log n) communication rounds. SIAM J. Comput. 35(1): 120\u2013131","journal-title":"SIAM J. Comput."},{"issue":"6","key":"47_CR18","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s00446-005-0127-6","volume":"18","author":"Z. Lotker","year":"2006","unstructured":"Lotker Z., Patt-Shamir B. and Peleg D. (2006). Distributed mst for constant diameter graphs. Distrib. Comput. 18(6): 453\u2013460","journal-title":"Distrib. Comput."},{"key":"47_CR19","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: Mst construction in o(log log n) communication rounds. In: Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures, pp. 94\u2013100 (2003)","DOI":"10.1145\/777412.777428"},{"key":"47_CR20","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality sensitive approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"47_CR21","doi-asserted-by":"crossref","unstructured":"Peleg, D., Rabinovich, V.: A near-tight lower bound on the time complexity of distributed mst construction. In: Proc. of the 40th IEEE Symp. on Foundations of Computer Science, pp. 253\u2013261 (1999)","DOI":"10.1109\/SFFCS.1999.814597"},{"issue":"3","key":"47_CR22","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D. Rosenkrantz","year":"1977","unstructured":"Rosenkrantz D., Stearns R. and Lewis P. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3): 563\u2013581","journal-title":"SIAM J. Comput."},{"key":"47_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0020419","volume-title":"Introduction to Distributed Algorithms","author":"G. Tel","year":"1994","unstructured":"Tel G. (1994). Introduction to Distributed Algorithms. Cambridge University Press, London"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0047-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-007-0047-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-007-0047-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T15:18:12Z","timestamp":1684077492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-007-0047-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,30]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["47"],"URL":"https:\/\/doi.org\/10.1007\/s00446-007-0047-8","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,30]]}}}