{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:22:51Z","timestamp":1778664171774,"version":"3.51.4"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T00:00:00Z","timestamp":1288569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-1999-14186"],"award-info":[{"award-number":["IST-1999-14186"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>\n            An (\u03b1, \u03b2)-spanner of an unweighted graph\n            <jats:italic>G<\/jats:italic>\n            is a subgraph\n            <jats:italic>H<\/jats:italic>\n            that distorts distances in\n            <jats:italic>G<\/jats:italic>\n            up to a multiplicative factor of \u03b1 and an additive term \u03b2. It is well known that any graph contains a (multiplicative) (2\n            <jats:italic>k<\/jats:italic>\n            \u22121, 0)-spanner of size\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            ) and an (additive) (1,2)-spanner of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ). However no other additive spanners are known to exist.\n          <\/jats:p>\n          <jats:p>\n            In this article we develop a couple of new techniques for constructing (\u03b1, \u03b2)-spanners. Our first result is an additive (1,6)-spanner of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ). The construction algorithm can be understood as an economical agent that assigns\n            <jats:italic>costs<\/jats:italic>\n            and\n            <jats:italic>values<\/jats:italic>\n            to paths in the graph,\n            <jats:italic>purchasing<\/jats:italic>\n            affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this\n            <jats:italic>path buying<\/jats:italic>\n            algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (\u03b1, \u03b2)-spanners can be computed efficiently, ideally in linear time. We show that, for any\n            <jats:italic>k<\/jats:italic>\n            , a (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            \u22121)-spanner with size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>kn<\/jats:italic>\n            <jats:sup>\n              1+1\/\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.\n          <\/jats:p>","DOI":"10.1145\/1868237.1868242","type":"journal-article","created":{"date-parts":[[2010,12,14]],"date-time":"2010-12-14T16:00:46Z","timestamp":1292342446000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Additive spanners and (\u03b1, \u03b2)-spanners"],"prefix":"10.1145","volume":"7","author":[{"given":"Surender","family":"Baswana","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.51"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132557"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 502--511","author":"Abraham I.","unstructured":"Abraham , I. , Bartal , Y. , and Neiman , O . 2007. Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 502--511 . Abraham, I., Bartal, Y., and Neiman, O. 2007. Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 502--511."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148144"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"B\u01cedoiu M.","unstructured":"B\u01cedoiu , M. , Indyk , P. , and Sidiropoulos , A . 2007. Approximation algorithms for embedding general metrics into trees . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). B\u01cedoiu, M., Indyk, P., and Sidiropoulos, A. 2007. Approximation algorithms for embedding general metrics into trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_50"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.29"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 672--681","author":"Baswana S.","unstructured":"Baswana , S. , Kavitha , T. , Mehlhorn , K. , and Pettie , S . 2005. New constructions of (&alpha;, \u03b2)-spanners and purely additive spanners . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 672--681 . Baswana, S., Kavitha, T., Mehlhorn, K., and Pettie, S. 2005. New constructions of (&alpha;, \u03b2)-spanners and purely additive spanners. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 672--681."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP).","author":"Baswana S.","unstructured":"Baswana , S. , and Sen , S . 2003. A simple linear time algorithm for computing a (2k&minus;1)-spanner of O(n1+1\/k) size in weighted graphs . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Baswana, S., and Sen, S. 2003. A simple linear time algorithm for computing a (2k&minus;1)-spanner of O(n1+1\/k) size in weighted graphs. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:4"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 414-- 423","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. , Coppersmith , D. , and Elkin , M . 2003. Sparse distance preservers and additive spanners . In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 414-- 423 . Bollob\u00e1s, B., Coppersmith, D., and Elkin, M. 2003. Sparse distance preservers and additive spanners. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 414-- 423."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_20"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109566"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 762--771","author":"Chan H. T.-H.","unstructured":"Chan , H. T.-H. , Gupta , A. , Maggs , B. M. , and Zhou , S . 2005. On hierarchical routing in doubling metrics . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 762--771 . Chan, H. T.-H., Gupta, A., Maggs, B. M., and Zhou, S. 2005. On hierarchical routing in doubling metrics. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 762--771."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669","author":"Coppersmith D.","unstructured":"Coppersmith , D. , and Elkin , M . 2005. Sparse source-wise and pair-wise distance preservers . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669 . Coppersmith, D., and Elkin, M. 2005. Sparse source-wise and pair-wise distance preservers. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Elkin M. 2004. Private communication.  Elkin M. 2004. Private communication.","DOI":"10.12968\/sece.2004.11.334"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380797"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.022"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). 261--270","author":"Emek Y.","unstructured":"Emek , Y. , and Peleg , D . 2004. Approximating minimum max-stretch spanning trees on unweighted graphs . In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). 261--270 . Emek, Y., and Peleg, D. 2004. Approximating minimum max-stretch spanning trees on unweighted graphs. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). 261--270."},{"key":"e_1_2_1_36_1","volume-title":"Theory of Graphs and its Applications","author":"Erd\u0151s P.","unstructured":"Erd\u0151s , P. 1963. Extremal problems in graph theory . In Theory of Graphs and its Applications . Publishing House of the Czechoslovak Academy of Sciences, Prague, Chechoslovakia, 29--36. Erd\u0151s, P. 1963. Extremal problems in graph theory. In Theory of Graphs and its Applications. Publishing House of the Czechoslovak Academy of Sciences, Prague, Chechoslovakia, 29--36."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 285--298","author":"Frigo M.","unstructured":"Frigo , M. , Leiserson , C. E. , Prokop , H. , and Ramachandran , S . 1999. Cache-oblivious algorithms . In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 285--298 . Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 285--298."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"e_1_2_1_40_1","unstructured":"Halperin S. and Zwick U. 1996. Unpublished.  Halperin S. and Zwick U. 1996. Unpublished."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Indyk P. and Matousek J. 2004. Low-distortion embedding of finite metric spaces. In Handbook of Discrete and Computational Geometry 2nd ed. CRC Press Boca Raton FL.  Indyk P. and Matousek J. 2004. Low-distortion embedding of finite metric spaces. In Handbook of Discrete and Computational Geometry 2nd ed. CRC Press Boca Raton FL.","DOI":"10.1201\/9781420035315.ch8"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Karp R. M. and Ramachandran V. 1990. Parallel algorithms for shared-memory machines. In Handbook of Computer Science. MIT Press Cambridge MA 869--942.   Karp R. M. and Ramachandran V. 1990. Parallel algorithms for shared-memory machines. In Handbook of Computer Science. MIT Press Cambridge MA 869--942.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/79"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Narasimhan G. and Smid M. 2007. Geometric Spanner Networks. Cambridge University Press Cambridge U.K.   Narasimhan G. and Smid M. 2007. Geometric Spanner Networks. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9780511546884"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394552"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 13th ACM-SIAM Symposium On Discrete Algorithms (SODA). 844-- 851","author":"Roditty L.","unstructured":"Roditty , L. , Thorup , M. , and Zwick , U . 2002. Roundtrip spanners and roundtrip routing in directed graphs . In Proceedings of the 13th ACM-SIAM Symposium On Discrete Algorithms (SODA). 844-- 851 . Roditty, L., Thorup, M., and Zwick, U. 2002. Roundtrip spanners and roundtrip routing in directed graphs. In Proceedings of the 13th ACM-SIAM Symposium On Discrete Algorithms (SODA). 844-- 851."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591","author":"Roditty L.","unstructured":"Roditty , L. , and Zwick , U . 2004. On dynamic shortest paths problems . In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591 . Roditty, L., and Zwick, U. 2004. On dynamic shortest paths problems. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90097-4"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.45"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 655--664","author":"Xiao J.","unstructured":"Xiao , J. , Liu , L. , Xia , L. , and Jiang , T . 2007. Fast elimination of redundant linear equations and reconstruction of recombination-free Mendelian inheritance on a pedigree . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 655--664 . Xiao, J., Liu, L., Xia, L., and Jiang, T. 2007. Fast elimination of redundant linear equations and reconstruction of recombination-free Mendelian inheritance on a pedigree. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 655--664."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1868237.1868242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1868237.1868242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:08:52Z","timestamp":1750248532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1868237.1868242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1868237.1868242"],"URL":"https:\/\/doi.org\/10.1145\/1868237.1868242","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}