{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:43:42Z","timestamp":1725543822611},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540354741"},{"type":"electronic","value":"9783540354758"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11780823_9","type":"book-chapter","created":{"date-parts":[[2006,6,23]],"date-time":"2006-06-23T14:45:59Z","timestamp":1151073959000},"page":"100-114","source":"Crossref","is-referenced-by-count":4,"title":["Fast Deterministic Distributed Algorithms for Sparse Spanners"],"prefix":"10.1007","author":[{"given":"Bilel","family":"Derbel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. Journal of the Association for Computing Machinery\u00a032, 804\u2013823 (1985)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"9_CR2","first-page":"230","volume-title":"19th Annual ACM Symposium on Theory of Computing (STOC)","author":"B. Awerbuch","year":"1987","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems. In: 19th Annual ACM Symposium on Theory of Computing (STOC), May 1987, pp. 230\u2013240. ACM Press, New York (1987)"},{"key":"9_CR3","first-page":"638","volume-title":"34th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"B. Awerbuch","year":"1993","unstructured":"Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Near-linear cost sequential and distributed constructions of sparse neighborhood coverss. In: 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), November 1993, pp. 638\u2013647. IEEE Computer Society Press, Los Alamitos (1993)"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jpdc.1996.0159","volume":"39","author":"B. Awerbuch","year":"1996","unstructured":"Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Fast distributed network decompositions and covers. Journal of Parallel and Distributed Computing\u00a039, 105\u2013114 (1996)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1137\/S0097539794271898","volume":"28","author":"B. Awerbuch","year":"1998","unstructured":"Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing\u00a028(1), 263\u2013277 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR6","first-page":"503","volume-title":"31th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions. In: 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1990, pp. 503\u2013513. IEEE Computer Society Press, Los Alamitos (1990)"},{"key":"9_CR7","first-page":"672","volume-title":"16th Symposium on Discrete Algorithms (SODA)","author":"S. Baswana","year":"2005","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1,\u03b2)-spanners and purely additive spanners. In: 16th Symposium on Discrete Algorithms (SODA), January 2005, pp. 672\u2013681. ACM-SIAM, New York (2005)"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k\u2009\u2212\u20091)-spanner of O(n 1\u2009+\u20091\/k ) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"key":"9_CR9","first-page":"271","volume-title":"15th Symposium on Discrete Algorithms (SODA)","author":"S. Baswana","year":"2004","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in $\\tilde{O}(n^2)$ time. In: 15th Symposium on Discrete Algorithms (SODA), January 2004, pp. 271\u2013280. ACM-SIAM, New York (2004)"},{"issue":"1","key":"9_CR10","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing\u00a028(1), 210\u2013236 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"9_CR11","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. Information and Control\u00a070(1), 32\u201353 (1986)","journal-title":"Information and Control"},{"issue":"1","key":"9_CR12","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L.J. Cowen","year":"2001","unstructured":"Cowen, L.J.: Compact routing with minimum stretch. Journal of Algorithms\u00a038(1), 170\u2013183 (2001)","journal-title":"Journal of Algorithms"},{"key":"9_CR13","volume-title":"20th IEEE International Parallel & Distributed Processing Symposium (IPDPS)","author":"B. Derbel","year":"2006","unstructured":"Derbel, B., Mosbah, M., Zemmari, A.: Fast distributed graph partition and application. In: 20th IEEE International Parallel & Distributed Processing Symposium (IPDPS), April 2006, IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0196-6774(03)00002-6","volume":"46","author":"T. Eilam","year":"2003","unstructured":"Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. Journal of Algorithms\u00a046, 97\u2013114 (2003)","journal-title":"Journal of Algorithms"},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/383962.383983","volume-title":"20th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"M. Elkin","year":"2001","unstructured":"Elkin, M.: Computing almost shortest paths. In: 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 53\u201362. ACM Press, New York (2001)"},{"key":"9_CR16","first-page":"359","volume-title":"15th Symposium on Discrete Algorithms (SODA)","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: 15th Symposium on Discrete Algorithms (SODA), January 2004, pp. 359\u2013368. ACM-SIAM, New York (2004)"},{"key":"9_CR17","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/1007352.1007407","volume-title":"36th Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problems. In: 36th Annual ACM Symposium on Theory of Computing (STOC), May 2004, pp. 331\u2013340. ACM Press, New York (2004)"},{"issue":"3","key":"9_CR18","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1\u2009+\u2009\u03b5,\u03b2)-spanner constructions for general graphs. SIAM Journal on Computing\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR19","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1145\/1011767.1011791","volume-title":"23rd Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1\u2009+\u2009\u03b5,\u03b2)-spanners in the distributed and streaming models. In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2004, pp. 160\u2013168. ACM Press, New York (2004)"},{"issue":"1","key":"9_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C. Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9renn\u00e8s, S., Raz, R.: Distance labeling in graphs. Journal of Algorithms\u00a053(1), 85\u2013112 (2004)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"9_CR21","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics\u00a01(4), 434\u2013446 (1988)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/11561927_21","volume-title":"Distributed Computing","author":"F. Kuhn","year":"2005","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 273\u2013287. Springer, Heidelberg (2005)"},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/1011767.1011811","volume-title":"23rd Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"F. Kuhn","year":"2004","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2004, pp. 300\u2013309. ACM Press, New York (2004)"},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1145\/1109557.1109666","volume-title":"17th Symposium on Discrete Algorithms (SODA)","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: 17th Symposium on Discrete Algorithms (SODA), January 2006, pp. 980\u2013989. ACM-SIAM, New York (2006)"},{"issue":"1","key":"9_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. Journal of Algorithms\u00a028(1), 40\u201366 (1998)","journal-title":"Journal of Algorithms"},{"key":"9_CR26","first-page":"331","volume-title":"28th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"N. Linial","year":"1987","unstructured":"Linial, N.: Distributive graph algorithms - Global solutions from local data. In: 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1987, pp. 331\u2013335. IEEE Computer Society Press, Los Alamitos (1987)"},{"issue":"1","key":"9_CR27","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graphs algorithms. SIAM Journal on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"9_CR28","first-page":"120","volume":"35","author":"Z. Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(loglogn) communication rounds. SIAM Journal on Discrete Mathematics\u00a035(1), 120\u2013131 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR29","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/383962.383984","volume-title":"20th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"Z. Lotker","year":"2001","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. In: 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 63\u201371. ACM Press, New York (2001)"},{"key":"9_CR30","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics\u00a013, 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"issue":"4","key":"9_CR31","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM Journal on Computing"},{"issue":"1-2","key":"9_CR32","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(98)00206-0","volume":"243","author":"S. Moran","year":"2000","unstructured":"Moran, S., Snir, S.: Simple and efficient network decomposition and synchronization. Theoretical Computer Science\u00a0243(1-2), 217\u2013241 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"9_CR33","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A. Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms\u00a020(2), 356\u2013374 (1996)","journal-title":"Journal of Algorithms"},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"5","key":"9_CR35","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"},{"issue":"4","key":"9_CR36","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchornizer for the hypercube. SIAM Journal on Computing\u00a018(4), 740\u2013747 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"9_CR37","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM\u00a036(3), 510\u2013530 (1989)","journal-title":"Journal of the ACM"},{"issue":"1-3","key":"9_CR38","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0166-218X(03)00368-8","volume":"141","author":"L.D. Penso","year":"2004","unstructured":"Penso, L.D., Valmir, C.B.: A distributed algorithm to find k-dominating sets. Discrete Applied Mathematics\u00a0141(1-3), 243\u2013253 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR39","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: 13th Symposium on Discrete Algorithms (SODA), January 2002, pp. 844\u2013851. ACM-SIAM (2002)"},{"key":"9_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"key":"9_CR41","first-page":"1","volume-title":"13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 2001, pp. 1\u201310. ACM Press, New York (2001)"},{"issue":"1","key":"9_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of the ACM"},{"issue":"1","key":"9_CR43","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0095-8956(91)90097-4","volume":"52","author":"R. Wenger","year":"1991","unstructured":"Wenger, R.: Extremal graphs with no C 4\u2019s, C 6\u2019s, or C 10\u2019s. Journal of Combinatorial Theory, Series B\u00a052(1), 113\u2013116 (1991)","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11780823_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,28]],"date-time":"2021-07-28T19:20:35Z","timestamp":1627500035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11780823_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354741","9783540354758"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/11780823_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}