{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:56:00Z","timestamp":1780073760063,"version":"3.54.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF","award":["2015813"],"award-info":[{"award-number":["2015813"]}]},{"name":"ISF","award":["724\/15 and 1718\/18"],"award-info":[{"award-number":["724\/15 and 1718\/18"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            Miller et al. [48] devised a distributed\n            <jats:sup>1<\/jats:sup>\n            algorithm in the CONGEST model that, given a parameter\n            <jats:italic>k<\/jats:italic>\n            = 1,2,\u2026, constructs an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )-spanner of an input unweighted\n            <jats:italic>n<\/jats:italic>\n            -vertex graph with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+1\/\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) expected edges in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) rounds of communication. In this article, we improve the result of Reference [48] by showing a\n            <jats:italic>k<\/jats:italic>\n            -round distributed algorithm in the same model that constructs a (2\n            <jats:italic>k<\/jats:italic>\n            \u22121)-spanner with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+1\/\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            }\/\u03f5) edges, with probability 1\u2212\u03f5 for any \u03f5&gt;0. Moreover, when\n            <jats:italic>k<\/jats:italic>\n            =\u03c9(log\n            <jats:italic>n<\/jats:italic>\n            ), our algorithm produces (still in\n            <jats:italic>k<\/jats:italic>\n            rounds)\n            <jats:italic>ultra-sparse<\/jats:italic>\n            spanners, i.e., spanners of size\n            <jats:italic>n<\/jats:italic>\n            (1+\n            <jats:italic>o<\/jats:italic>\n            (1)), with probability 1\u2212\n            <jats:italic>o<\/jats:italic>\n            (1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that are sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large\n            <jats:italic>k<\/jats:italic>\n            , it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm.\n          <\/jats:p>\n          <jats:p>\n            We also devise improved bounds (and algorithms realizing these bounds) for (1+\u03f5, \u03b2)-spanners and emulators. In particular, we show that for any unweighted\n            <jats:italic>n<\/jats:italic>\n            -vertex graph and any \u03f5 &gt; 0, there exists a (1+ \u03f5, (log log\n            <jats:italic>n<\/jats:italic>\n            \/ \u03f5)\n            <jats:sup>\n              log log\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            )-emulator with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) edges. All previous constructions of (1+\u03f5, \u03b2)-spanners and emulators employ a superlinear number of edges for all choices of parameters.\n          <\/jats:p>\n          <jats:p>Finally, we provide some applications of our results to approximate shortest paths\u2019 computation in unweighted graphs.<\/jats:p>","DOI":"10.1145\/3274651","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Efficient Algorithms for Constructing Very Sparse Spanners and Emulators"],"prefix":"10.1145","volume":"15","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897555"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039722"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.08.003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_2_1_7_1","unstructured":"Stephen Alstrup Soren Dahlgaard Arnold Filtser Morten Stockel and Christian Wulff-Nilsen. 2017. Personal communication.  Stephen Alstrup Soren Dahlgaard Arnold Filtser Morten Stockel and Christian Wulff-Nilsen. 2017. Personal communication."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366823"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"e_1_2_1_12_1","unstructured":"Ajesh Babu and Jaikumar Radhakrishnan. 2010. An entropy based proof of the Moore bound for irregular graphs. CoRR abs\/1011.1058 (2010). http:\/\/arxiv.org\/abs\/1011.1058  Ajesh Babu and Jaikumar Radhakrishnan. 2010. An entropy based proof of the Moore bound for irregular graphs. CoRR abs\/1011.1058 (2010). http:\/\/arxiv.org\/abs\/1011.1058"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_10"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming LNCS","volume":"2719","author":"Baswana S."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1255378.1255381"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9444-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688103"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103431046"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627853"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366822"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899057"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_2_1_30_1","unstructured":"D. Dubhashi A. Mei A. Panconesi J. Radhakrishnan and A. Srinivisan. 2003. Fast Distributed Algorithm for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. 717--724.   D. Dubhashi A. Mei A. Panconesi J. Radhakrishnan and A. Srinivisan. 2003. Fast Distributed Algorithm for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. 717--724."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007407"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394624"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933094"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.22"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039728"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722184"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2836167"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the ACM-SIAM Symp. on Discrete Algorithms. 745--754","author":"Feigenbaum J."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933114"},{"key":"e_1_2_1_45_1","unstructured":"S. Halperin and U. Zwick. 1996. Linear time deterministic algorithm for computing spanners for unweighted graphs. (unpublished).  S. Halperin and U. Zwick. 1996. Linear time deterministic algorithm for computing spanners for unweighted graphs. (unpublished)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.03.001"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/647680.732175"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_2_1_58_1","unstructured":"Seth Pettie. 2016. Personal communication.  Seth Pettie. 2016. Personal communication."},{"key":"e_1_2_1_59_1","unstructured":"John H. Reif. 1993. Synthesis of Parallel Algorithms (1st ed.). Morgan Kaufmann Publishers Inc. San Francisco CA.   John H. Reif. 1993. Synthesis of Parallel Algorithms (1st ed.). Morgan Kaufmann Publishers Inc. San Francisco CA."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms. 802--809","author":"Thorup M."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274651","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274651","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:56Z","timestamp":1750208276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274651"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3274651"],"URL":"https:\/\/doi.org\/10.1145\/3274651","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}