{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:41:34Z","timestamp":1742395294438},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540446248"},{"type":"electronic","value":"9783540446279"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11864219_25","type":"book-chapter","created":{"date-parts":[[2006,10,4]],"date-time":"2006-10-04T05:25:39Z","timestamp":1159939539000},"page":"355-369","source":"Crossref","is-referenced-by-count":11,"title":["A Fast Distributed Approximation Algorithm for Minimum Spanning Trees"],"prefix":"10.1007","author":[{"given":"Maleq","family":"Khan","sequence":"first","affiliation":[]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R. Gallager","year":"1983","unstructured":"Gallager, R., Humblet, P., Spira, P.: A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems\u00a05(1), 66\u201377 (1983)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"doi-asserted-by":"crossref","unstructured":"Chin, F., Ting, H.: An almost linear time and O(n log n + e) messages distributed algorithm for minimum-weight spanning trees. In: Proc. 26th IEEE Symp. Foundations of Computer Science, pp. 257\u2013266 (1985)","key":"25_CR2","DOI":"10.1109\/SFCS.1985.7"},{"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)","key":"25_CR3","DOI":"10.1145\/323596.323612"},{"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)","key":"25_CR4","DOI":"10.1145\/28395.28421"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J. Garay","year":"1998","unstructured":"Garay, J., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput.\u00a027, 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"key":"25_CR6","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 k-dominating sets and applications. J. Algorithms\u00a028, 40\u201366 (1998)","journal-title":"J. Algorithms"},{"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)","key":"25_CR7"},{"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)","key":"25_CR8","DOI":"10.1109\/SFFCS.1999.814597"},{"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)","key":"25_CR9","DOI":"10.1145\/1007352.1007407"},{"issue":"4","key":"25_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: An overview of distributed approximation. ACM SIGACT News Distributed Computing Column\u00a035(4), 40\u201357 (2004)","journal-title":"ACM SIGACT News Distributed Computing Column"},{"key":"25_CR11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"25_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(89)90103-5","volume":"64","author":"E. Korach","year":"1989","unstructured":"Korach, E., Moran, S., Zaks, S.: Optimal lower bounds for some distributed algorithms for a complete network of processors. Theoretical Computer Science\u00a064, 125\u2013132 (1989)","journal-title":"Theoretical Computer Science"},{"key":"25_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0020419","volume-title":"Introduction to Distributed Algorithms","author":"G. Tel","year":"1994","unstructured":"Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge (1994)"},{"unstructured":"Khan, M., Kumar, V.A., Pandurangan, G.: A simple randomized scheme for constructing low-cost spanning subgraphs with applications to distributed algorithms.Technical Report, Dept. of Computer Science, Purdue University (2005), http:\/\/www.cs.purdue.edu\/homes\/gopal\/localmst.pdf","key":"25_CR14"},{"issue":"3","key":"25_CR15","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D. Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D., Stearns, R., Lewis, P.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput.\u00a06(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"25_CR16","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"Imase, M., Waxman, B.: Dynamic steiner tree problem. Siam J. Discrete Math.\u00a04(3), 369\u2013384 (1991)","journal-title":"Siam J. Discrete Math."},{"issue":"2","key":"25_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/0216019","volume":"16","author":"E. Korach","year":"1987","unstructured":"Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM Journal of Computing\u00a016(2), 231\u2013236 (1987)","journal-title":"SIAM Journal of Computing"},{"issue":"1","key":"25_CR18","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 $\\textit{O}(\\log \\log n)$ communication rounds. SIAM J. Comput.\u00a035(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed mst for constant diameter graphs. In: Proc. of the 20th ACM Symp. on Principles of Distributed Computing, pp. 63\u201372 (2001)","key":"25_CR19","DOI":"10.1145\/383962.383984"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability for sums of bounded random variables. J. of the American Statistical Association\u00a058, 13\u201330 (1963)","journal-title":"J. of the American Statistical Association"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11864219_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:44:51Z","timestamp":1605642291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11864219_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540446248","9783540446279"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11864219_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}