{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:37:58Z","timestamp":1725507478712},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770954"},{"type":"electronic","value":"9783540770961"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77096-1_12","type":"book-chapter","created":{"date-parts":[[2008,4,11]],"date-time":"2008-04-11T07:44:46Z","timestamp":1207899886000},"page":"159-173","source":"Crossref","is-referenced-by-count":2,"title":["Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs"],"prefix":"10.1007","author":[{"given":"Sven O.","family":"Krumke","sequence":"first","affiliation":[]},{"given":"Peter","family":"Merz","sequence":"additional","affiliation":[]},{"given":"Tim","family":"Nonner","sequence":"additional","affiliation":[]},{"given":"Katharina","family":"Rupp","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"12_CR1","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. ACM\u00a041(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"key":"12_CR2","unstructured":"Jothi, R., Raghavachari, B., Varadarajan, S.: A 5\/4-approximation algorithm for minimum 2-edge-connectivity. In: SODA 2003: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 725\u2013734 (2003)"},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jagm.1993.1010","volume":"14","author":"S. Khuller","year":"1993","unstructured":"Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms\u00a014(2), 214\u2013225 (1993)","journal-title":"J. Algorithms"},{"issue":"1","key":"12_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R.G. Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst.\u00a05(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1145\/28395.28421","volume-title":"STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing","author":"B. Awerbuch","year":"1987","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 230\u2013240. ACM Press, New York (1987)"},{"key":"12_CR6","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: SODA 2004: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 359\u2013368 (2004)"},{"key":"12_CR7","unstructured":"Fernandes, C.G.: A better approximation ratio for the minimum k-edge-connected spanning subgraph problem. In: SODA 1997: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp. 629\u2013638 (1997)"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing, A Locality-Sensitive Approach. Siam, Philadelphia (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"6","key":"12_CR9","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1109\/TCOM.1983.1095883","volume":"31","author":"P.A. Humblet","year":"1983","unstructured":"Humblet, P.A.: A distributed algorithm for minimum weight directed spanning trees. IEEE Trans. Comm.\u00a031(6), 756\u2013762 (1983)","journal-title":"IEEE Trans. Comm."},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. Gabow","year":"1986","unstructured":"Gabow, H., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica\u00a06(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"12_CR11","unstructured":"Pritchard, D.: Robust network computation. Master\u2019s thesis, Massachusetts Institute of Technology (August 2005)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Thurimella, R.: Sub-linear distributed algorithms for sparse certificates and biconnected components (extended abstract). In: PODC 1995: Symposium on Principles of Distributed Computing, pp. 28\u201337 (1995)","DOI":"10.1145\/224964.224968"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"ICALP 2007","author":"A. Korman","year":"2007","unstructured":"Korman, A.: Labeling schemes for vertex connectivity. In: Arge, L., Gachin, C., Jurdzinshi, T., Taoledci, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, Springer, Heidelberg (2007)"},{"issue":"2","key":"12_CR14","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(99)00283-2","volume":"245","author":"C. Gavoille","year":"2000","unstructured":"Gavoille, C.: A survey on interval routing. Theor. Comput. Sci.\u00a0245(2), 217\u2013253 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR15","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Quart. Appl. Math.\u00a016, 87\u201390 (1958)","journal-title":"Quart. Appl. Math."},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1145\/564870.564914","volume-title":"SPAA 2002: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures","author":"S. Alstrup","year":"2002","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: SPAA 2002: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, pp. 258\u2013264. ACM Press, New York (2002)"},{"issue":"5","key":"12_CR17","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D. Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing\u00a030(5), 1427\u20131442 (2000)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77096-1_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:00:04Z","timestamp":1619506804000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77096-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540770954","9783540770961"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77096-1_12","relation":{},"subject":[]}}