{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T18:47:06Z","timestamp":1790189226316,"version":"4.1.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>A $t$-spanner of a weighted undirected graph $G=(V,E)$, is a subgraph $H$ such that $d_H(u,v)\\le t\\cdot d_G(u,v)$ for all $u,v\\in V$. The sparseness of the spanner can be measured by its size (the number of edges) and weight (the sum of all edge weights), both being important measures of the spanner's quality; in this work we focus on the latter. Specifically, it is shown that for any parameters $k\\ge 1$ and $\\varepsilon&gt;0$, any weighted graph $G$ on $n$ vertices admits a $(2k-1)\\cdot(1+\\varepsilon)$-stretch spanner of weight at most $w(MST(G))\\cdot O_\\varepsilon(kn^{1\/k}\/\\log k)$, where $w(MST(G))$ is the weight of a minimum spanning tree of $G$. Our result is obtained via a novel analysis of the classic greedy algorithm and improves previous work by a factor of $O(\\log k)$.<\/jats:p>","DOI":"10.1137\/140979538","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T15:34:34Z","timestamp":1438270474000},"page":"1312-1321","source":"Crossref","is-referenced-by-count":10,"title":["Light Spanners"],"prefix":"10.1137","volume":"29","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"atypb2","first-page":"489","author":"Arya S.","year":"1995","journal-title":"New York"},{"key":"atypb3","first-page":"177","author":"Awerbuch B.","year":"1990","journal-title":"New York"},{"key":"atypb4","unstructured":"B. Awerbuch, A. Baratz, and D. Peleg,\n                      Efficient Broadcast and Light-Weight Spanners\n                      , manuscript, 1991."},{"key":"atypb5","first-page":"384","author":"Baswana S.","year":"2003","journal-title":"The Netherlands"},{"key":"atypb6","unstructured":"B. Bolloba\u0301s,\n                      Extremal Graph Theory\n                      , Academic Press, London, 1978."},{"key":"atypb7","unstructured":"R. Braynard, D. Kostic, A. Rodriguez, J. Chase, and A. Vahdat,\n                      Opus: An overlay peer utility service\n                      , in Proceedings of the 5th OPENARCH, New York, NY, 2002."},{"key":"atypb8","first-page":"315","author":"Chan T.-H. H.","year":"2013","journal-title":"New York"},{"key":"atypb9","first-page":"192","author":"Chandra B.","year":"1992","journal-title":"New York"},{"key":"atypb10","first-page":"648","author":"Cohen E.","year":"1993","journal-title":"Washington, DC"},{"key":"atypb11","first-page":"53","author":"Das G.","year":"1993","journal-title":"New York"},{"key":"atypb12","first-page":"519","author":"Dinitz Y.","year":"2008","journal-title":"Washington, DC"},{"key":"atypb13","first-page":"645","author":"Elkin M.","year":"2013","journal-title":"New York"},{"key":"atypb14","first-page":"387","author":"Gottlieb L.","year":"2014","journal-title":"New York"},{"key":"atypb15","first-page":"869","author":"Grigni M.","year":"2000","journal-title":"New York"},{"key":"atypb16","first-page":"467","author":"Grigni M.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb17","first-page":"365","author":"Kanj I. A.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb18","unstructured":"D. Kostic and A. Vahdat,\n                      Latency Versus Cost Optimizations in Hierarchical Overlay Networks\n                      , Technical report, Duke University, Durham, NC, 2002."},{"key":"atypb19","unstructured":"Y. Mansour and D. Peleg,\n                      An Approximation Algorithm for Minimum-Cost Network Design\n                      , Technical report, Weizmann Institute of Science, Rehovot, Israel, 1998."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"D. Peleg,\n                      Distributed Computing: A Locality-Sensitive Approach\n                      , SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719772"},{"key":"atypb21","first-page":"261","author":"Roditty L.","year":"2005","journal-title":"Berlin"},{"key":"atypb22","first-page":"580","author":"Roditty L.","year":"2004","journal-title":"The Netherlands"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2053381"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/net.10019"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140979538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:45Z","timestamp":1787318265000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140979538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140979538"],"URL":"https:\/\/doi.org\/10.1137\/140979538","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}