{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:51Z","timestamp":1759638951351},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540751410"},{"type":"electronic","value":"9783540751427"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75142-7_16","type":"book-chapter","created":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T14:00:46Z","timestamp":1189000846000},"page":"179-192","source":"Crossref","is-referenced-by-count":5,"title":["Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time"],"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"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J. ACM\u00a032, 804\u2013823 (1985)","journal-title":"J. ACM"},{"key":"16_CR2","first-page":"638","volume-title":"34th IEEE Symp. on Foundations of Computer Science","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 IEEE Symp. on Foundations of Computer Science, pp. 638\u2013647. IEEE Computer Society Press, Los Alamitos (1993)"},{"key":"16_CR3","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. J. Parallel and Distributed Computing\u00a039, 105\u2013114 (1996)","journal-title":"J. Parallel and Distributed Computing"},{"key":"16_CR4","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 neighbourhood covers. SIAM J. on Computing\u00a028, 263\u2013277 (1998)","journal-title":"SIAM J. on Computing"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1109\/SFCS.1989.63504","volume-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science","author":"B. Awerbuch","year":"1989","unstructured":"Awerbuch, B., Goldberg, A., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364\u2013369. IEEE Computer Society Press, Los Alamitos (1989)"},{"key":"16_CR6","first-page":"503","volume-title":"31th IEEE Symp. on Foundations of Computer Science","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions. In: 31th IEEE Symp. on Foundations of Computer Science, pp. 503\u2013513. IEEE Computer Society Press, Los Alamitos (1990)"},{"key":"16_CR7","first-page":"672","volume-title":"16th ACM-SIAM Symp. on Discrete Algorithms","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 ACM-SIAM Symp. on Discrete Algorithms, pp. 672\u2013681. ACM Press, New York (2005)"},{"key":"16_CR8","first-page":"271","volume-title":"15th ACM-SIAM Symp. on Discrete Algorithms","author":"S. Baswana","year":"2004","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \n                    \n                      \n                    \n                    $\\tilde{O}(n^2)$\n                   time. In: 15th ACM-SIAM Symp. on Discrete Algorithms, pp. 271\u2013280. ACM Press, New York (2004)"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S. Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures and Algorithms\u00a030, 532\u2013563 (2007)","journal-title":"Random Structures and Algorithms"},{"key":"16_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 J. on Computing\u00a028, 210\u2013236 (1998)","journal-title":"SIAM J. on Computing"},{"key":"16_CR11","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. J. Algorithms\u00a038, 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/11780823_9","volume-title":"Structural Information and Communication Complexity","author":"B. Derbel","year":"2006","unstructured":"Derbel, B., Gavoille, C.: Fast deterministic distributed algorithms for sparse spanners. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 100\u2013114. Springer, Heidelberg (2006)"},{"key":"16_CR13","volume-title":"20th IEEE Int. Parallel and Distributed Processing Symp.","author":"B. Derbel","year":"2006","unstructured":"Derbel, B., Mosbah, M., Zemmari, A.: Fast distributed graph partition and application. In: 20th IEEE Int. Parallel and Distributed Processing Symp., IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All pairs almost shortest paths. SIAM J. Computing\u00a029, 1740\u20131759 (2000)","journal-title":"SIAM J. Computing"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/j.jcss.2005.04.002","volume":"71","author":"D. Dubhashi","year":"2005","unstructured":"Dubhashi, D., Mai, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. of Computer and System Sciences\u00a071, 467\u2013479 (2005)","journal-title":"J. of Computer and System Sciences"},{"key":"16_CR16","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. J. Algorithms\u00a046, 97\u2013114 (2003)","journal-title":"J. Algorithms"},{"key":"16_CR17","first-page":"53","volume-title":"20th ACM Symp. on Principles of Distributed Computing","author":"M. Elkin","year":"2001","unstructured":"Elkin, M.: Computing almost shortest paths. In: 20th ACM Symp. on Principles of Distributed Computing, pp. 53\u201362. ACM Press, New York (2001)"},{"key":"16_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 J. on Computing\u00a033, 608\u2013631 (2004)","journal-title":"SIAM J. on Computing"},{"key":"16_CR19","first-page":"160","volume-title":"23rd ACM Symp. on Principles of Distributed Computing","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 ACM Symp. on Principles of Distributed Computing, pp. 160\u2013168. ACM Press, New York (2004)"},{"key":"16_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. J. Algorithms\u00a053, 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"16_CR21","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, 217\u2013241 (2000)","journal-title":"Theoretical Computer Science"},{"key":"16_CR22","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. J. Algorithms\u00a020, 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"16_CR23","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"},{"key":"16_CR24","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 J. Computing\u00a018, 740\u2013747 (1989)","journal-title":"SIAM J. Computing"},{"key":"16_CR25","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. J. ACM\u00a036, 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_9","volume-title":"34 th International Colloquium on Automata, Languages and Programming","author":"S. Pettie","year":"2007","unstructured":"Pettie, S.: Low distortion spanners. In: 34\n                    th\n                   International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a04596, Springer, Heidelberg (2007)"},{"key":"16_CR27","first-page":"844","volume-title":"13th ACM-SIAM Symp. on Discrete Algorithms","author":"L. Roditty","year":"2002","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: 13th ACM-SIAM Symp. on Discrete Algorithms, pp. 844\u2013851. ACM Press, New York (2002)"},{"key":"16_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"16_CR29","first-page":"1","volume-title":"13th ACM Symp. on Parallel Algorithms and Architectures","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th ACM Symp. on Parallel Algorithms and Architectures, pp. 1\u201310. ACM Press, New York (2001)"},{"key":"16_CR30","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. J. ACM\u00a052, 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"16_CR31","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1145\/1109557.1109645","volume-title":"17th ACM-SIAM Symp. on Discrete Algorithm","author":"M. Thorup","year":"2006","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: 17th ACM-SIAM Symp. on Discrete Algorithm, pp. 802\u2013809. ACM Press, New York (2006)"},{"key":"16_CR32","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\n                  4\u2019s, C\n                  6\u2019s, or C\n                  10\u2019s. J. Combinatorial Theory, Series B\u00a052, 113\u2013116 (1991)","journal-title":"J. Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75142-7_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:52:36Z","timestamp":1619520756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75142-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540751410","9783540751427"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75142-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}