{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T10:37:27Z","timestamp":1773830247468,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,8,18]],"date-time":"2008-08-18T00:00:00Z","timestamp":1219017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2008,8,18]]},"DOI":"10.1145\/1400751.1400788","type":"proceedings-article","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T12:38:39Z","timestamp":1219149519000},"page":"273-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["On the locality of distributed sparse spanner construction"],"prefix":"10.1145","author":[{"given":"Bilel","family":"Derbel","sequence":"first","affiliation":[{"name":"University, Lille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[{"name":"University, Bordeaux, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Viennot","sequence":"additional","affiliation":[{"name":"INRIA, University Paris 7, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,18]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148143"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0159"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794271898"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.29"},{"key":"e_1_3_2_1_6_1","first-page":"672","volume-title":"16th Symposium on Discrete Algorithms (SODA), ACM-SIAM","author":"Baswana S.","year":"2005","unstructured":"S. Baswana , T. Kavitha , K. Mehlhorn , and S. Pettie , New constructions of (\u03b1,\u03b2)-spanners and purely additive spanners , in 16th Symposium on Discrete Algorithms (SODA), ACM-SIAM , Jan. 2005 , pp. 672 -- 681 . S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie, New constructions of (\u03b1,\u03b2)-spanners and purely additive spanners, in 16th Symposium on Discrete Algorithms (SODA), ACM-SIAM, Jan. 2005, pp. 672--681."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-109-8"},{"key":"e_1_3_2_1_9_1","first-page":"414","volume-title":"14th Symposium on Discrete Algorithms (SODA), ACM-SIAM","author":"Bollob\u00e1s B.","year":"2003","unstructured":"B. Bollob\u00e1s , D. Coppersmith , and M. Elkin , Sparse distance preservers and additive spanners , in 14th Symposium on Discrete Algorithms (SODA), ACM-SIAM , Jan. 2003 , pp. 414 -- 423 . B. Bollob\u00e1s, D. Coppersmith, and M. Elkin, Sparse distance preservers and additive spanners, in 14th Symposium on Discrete Algorithms (SODA), ACM-SIAM, Jan. 2003, pp. 414--423."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"e_1_3_2_1_11_1","first-page":"660","volume-title":"16th Symposium on Discrete Algorithms (SODA), ACM-SIAM","author":"Coppersmith D.","year":"2005","unstructured":"D. Coppersmith and M. Elkin , Sparse source-wise and pair-wise distance preservers , in 16th Symposium on Discrete Algorithms (SODA), ACM-SIAM , Jan. 2005 , pp. 660 -- 669 . D. Coppersmith and M. Elkin, Sparse source-wise and pair-wise distance preservers, in 16th Symposium on Discrete Algorithms (SODA), ACM-SIAM, Jan. 2005, pp. 660--669."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"B.\n      Derbel C.\n      Gavoille and \n      D.\n      Peleg Deterministic distributed construction of linear stretch spanners in polylogarithmic time in $21^st$ International Symposium on Distributed Computing (DISC) vol. \n  4731\n   of \n  Lecture Notes in Computer Science Springer Sept. \n  2007 pp. \n  179\n  --\n  192\n  .   B. Derbel C. Gavoille and D. Peleg Deterministic distributed construction of linear stretch spanners in polylogarithmic time in $21^st$ International Symposium on Distributed Computing (DISC) vol. 4731 of Lecture Notes in Computer Science Springer Sept. 2007 pp. 179--192.","DOI":"10.1007\/978-3-540-75142-7_16"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.04.002"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_3_2_1_15_1","volume-title":"Nov.","author":"Elkin M.","year":"2006","unstructured":"M. Elkin , A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners, tech. rep., arXiv:cs.DS\/0611001v1 , Nov. 2006 . ______, A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners, tech. rep., arXiv:cs.DS\/0611001v1, Nov. 2006."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011791"},{"key":"e_1_3_2_1_19_1","first-page":"29","volume-title":"Publ","author":"Erd\u00f6s P.","year":"1964","unstructured":"P. Erd\u00f6s , Extremal problems in graph theory , in Publ . House Cszechoslovak Acad . Sci., Prague, 1964 , pp. 29 -- 36 . P. Erd\u00f6s, Extremal problems in graph theory, in Publ. House Cszechoslovak Acad. Sci., Prague, 1964, pp. 29--36."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579234"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00259-2"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009804"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073826"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_3_2_1_25_1","first-page":"73","volume-title":"Bulletin of the American Mathematical Society (New Series), 32","author":"Lazebnik F.","year":"1995","unstructured":"F. Lazebnik , V. A. Ustimenko , and A. J. Woldar , A new series of dense graphs of high girth , Bulletin of the American Mathematical Society (New Series), 32 ( 1995 ), pp. 73 -- 79 . F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, A new series of dense graphs of high girth, Bulletin of the American Mathematical Society (New Series), 32 (1995), pp. 73--79."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_27_1","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"Peleg D.","year":"2000","unstructured":"D. Peleg , Distributed Computing: A Locality-Sensitive Approach , SIAM Monographs on Discrete Mathematics and Applications , 2000 . D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications, 2000."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_3_2_1_30_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-540-73420-8_9","volume-title":"34th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Pettie S.","year":"2007","unstructured":"S. Pettie , Low distortion spanners , in 34th International Colloquium on Automata, Languages and Programming (ICALP) , vol. 4596 of Lecture Notes in Computer Science , Springer , July 2007 , pp. 78 -- 89 . S. Pettie, Low distortion spanners, in 34th International Colloquium on Automata, Languages and Programming (ICALP), vol. 4596 of Lecture Notes in Computer Science, Springer, July 2007, pp. 78--89."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90097-4"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.45"}],"event":{"name":"PODC '08: ACM Symposium on Principles of Distributed Computing","location":"Toronto Canada","acronym":"PODC '08","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1400751.1400788","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1400751.1400788","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:23Z","timestamp":1750258043000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1400751.1400788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,18]]},"references-count":35,"alternative-id":["10.1145\/1400751.1400788","10.1145\/1400751"],"URL":"https:\/\/doi.org\/10.1145\/1400751.1400788","relation":{},"subject":[],"published":{"date-parts":[[2008,8,18]]},"assertion":[{"value":"2008-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}