{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T10:37:22Z","timestamp":1773830242348,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T00:00:00Z","timestamp":1532304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Science Foundation","award":["1696\/14"],"award-info":[{"award-number":["1696\/14"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,23]]},"DOI":"10.1145\/3212734.3212758","type":"proceedings-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T16:28:33Z","timestamp":1533054513000},"page":"139-148","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Distributed Spanner Approximation"],"prefix":"10.1145","author":[{"given":"Keren","family":"Censor-Hillel","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Michal","family":"Dory","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2018,7,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_3"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129767"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89572"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"e_1_3_2_1_5_1","unstructured":"Leonid Barenboim Michael Elkin and Cyril Gavoille. 2016. A fast networkdecomposition algorithm and its applications to constant-time distributed computation. Theoretical Computer Science (2016).  Leonid Barenboim Michael Elkin and Cyril Gavoille. 2016. A fast networkdecomposition algorithm and its applications to constant-time distributed computation. Theoretical Computer Science (2016)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"e_1_3_2_1_9_1","volume-title":"Finding Sparser Directed Spanners. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 424--435","author":"Berman Piotr","year":"2010"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Keren Censor-Hillel and Michal Dory. 2018. Distributed Spanner Approximation. arXiv:1802.03160 (2018). https:\/\/arxiv.org\/abs\/1802.03160  Keren Censor-Hillel and Michal Dory. 2018. Distributed Spanner Approximation. arXiv:1802.03160 (2018). https:\/\/arxiv.org\/abs\/1802.03160","DOI":"10.1145\/3212734.3212758"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_10"},{"key":"e_1_3_2_1_12_1","volume-title":"Quadratic and NearQuadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing, DISC 2017","author":"Censor-Hillel Keren","year":"2017"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484268"},{"key":"e_1_3_2_1_15_1","unstructured":"Eden Chlamt\u00e1c and Michael Dinitz. 2014. Lowest Degree k-Spanner: Approximation and Hardness. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). 80--95.  Eden Chlamt\u00e1c and Michael Dinitz. 2014. Lowest Degree k-Spanner: Approximation and Hardness. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). 80--95."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039720"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.61"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9190-x"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818375"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993680"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993830"},{"key":"e_1_3_2_1_23_1","volume-title":"Distributed Distance-Bounded Network Design Through Distributed Convex Programming. In 21st International Conference on Principles of Distributed Systems, OPODIS","author":"Dinitz Michael","year":"2017"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884494"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212760"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441058"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039728"},{"key":"e_1_3_2_1_31_1","volume-title":"8th International Colloquium on Structural Information and Communication Complexity (SIROCCO). 117--132","author":"Elkin Michael","year":"2001"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.022"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1266-2"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011791"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of Symposium Smolenice. Publ. House Cszechoslovak Acad. Sci., Prague, 29--36","author":"Erd's Paul","year":"1964"},{"key":"e_1_3_2_1_36_1","unstructured":"Orr Fischer Tzlil Gonen and Rotem Oshman. 2017. Distributed Property Testing for Subgraph-Freeness Revisited. CoRR abs\/1705.04033 (2017).  Orr Fischer Tzlil Gonen and Rotem Oshman. 2017. Distributed Property Testing for Subgraph-Freeness Revisited. CoRR abs\/1705.04033 (2017)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095207"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_40_1","volume-title":"Improved Deterministic Distributed Construction of Spanners. In 31st International Symposium on Distributed Computing, DISC 2017","author":"Grossman Ofer","year":"2017"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897533"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332504"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/777474.777476"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0021-y"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268753"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872040"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY USA.   Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY USA.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260763"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367069"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"}],"event":{"name":"PODC '18: ACM Symposium on Principles of Distributed Computing","location":"Egham United Kingdom","acronym":"PODC '18","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3212734.3212758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3212734.3212758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:44Z","timestamp":1750212464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3212734.3212758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,23]]},"references-count":62,"alternative-id":["10.1145\/3212734.3212758","10.1145\/3212734"],"URL":"https:\/\/doi.org\/10.1145\/3212734.3212758","relation":{},"subject":[],"published":{"date-parts":[[2018,7,23]]},"assertion":[{"value":"2018-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}