{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:27Z","timestamp":1787337507230,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>A k-spanner of a connected (undirected unweighted) graph G=(V,E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than that distance in G by no more than a factor of k. This paper is concerned with approximating the problem of finding a 2-spanner in a given graph, with minimum maximum degree. We first show that the problem is at least as hard to approximate as set cover. Then a randomized approximation algorithm is provided for this problem, with approximation ratio of $\\tilde O(\\Delta^{1\/4})$. We then present a probabilistic algorithm that is more efficient for sparse graphs. Our algorithms are converted into deterministic ones using derandomization.<\/jats:p>","DOI":"10.1137\/s0097539794268753","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1438-1456","source":"Crossref","is-referenced-by-count":20,"title":["Generating Low-Degree 2-Spanners"],"prefix":"10.1137","volume":"27","author":[{"given":"Guy","family":"Kortsarz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"B. Awerbuch, A. Baratz, and D. Peleg,\n                      Efficient Broadcast and Light\u2010Weight Spanners\n                      , 1991, manuscript."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Ingo Alth\u00f6fer, Gautam Das, David Dobkin, Deborah Joseph, Generating sparse spanners for weighted graphs, Lecture Notes in Comput. Sci., Vol. 447, Springer, Berlin, 1990, 26\u2013371076014","DOI":"10.1007\/3-540-52846-6_75"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Michael Molloy, The probabilistic method, Algorithms Combin., Vol. 16, Springer, Berlin, 1998, 1\u2013351678558","DOI":"10.1007\/978-3-662-12788-9_1"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell,\n                      Efficient probabilistically checkable proofs: Applications to approximation\n                      , in Proc. 25th ACM Symposium on the Theory of Computing, 1993, pp. 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"R5","unstructured":"L. Cai,\n                      Tree 2\u2010spanners\n                      , Technical Report 91\u20104, Simon Fraser University, Burnaby, BC, 1991."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000088"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"D. P. Dobkin, S. J. Friedman, and K. J. Supowit,\n                      Delaunay graphs are almost as good as complete graphs\n                      , in Proc. 31st IEEE Symp. on Foundations of Computer Science, 1987, pp. 20\u201326.","DOI":"10.1109\/SFCS.1987.18"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"G. Das and D. Joseph,\n                      Which triangulation approximates the complete graph?\n                      in International Symposium on Optimal Algorithms, Vol. LNCS\u2010401, Springer\u2010Verlag, Berlin, New York, 1989, pp. 168\u2013192.","DOI":"10.1007\/3-540-51859-2_15"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      A threshold of lnn for approximating set cover\n                      , in Proc. ACM STOC, 1996.","DOI":"10.1145\/237814.237977"},{"key":"R12","unstructured":"H. Flanders,\n                      Calculus\n                      , W. H. Freeman & Co., San Francisco, CA, 1985."},{"key":"R13","volume-title":"An introduction to the theory of numbers","author":"Niven Ivan","year":"1991"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"R16","first-page":"1","author":"Khachiyan L.","year":"1980","journal-title":"Yingyong Shuxue yu Jisuan Shuxue"},{"key":"R17","doi-asserted-by":"crossref","first-page":"1438","DOI":"10.1137\/S0097539794268753","volume":"27","author":"Kortsarz Guy","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Christos Levcopoulos, Andrzej Lingas, There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees, Lecture Notes in Comput. Sci., Vol. 401, Springer, Berlin, 1989, 9\u2013131048153","DOI":"10.1007\/3-540-51859-2_2"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1024"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230417"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230206"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis,\n                      On the hardness of approximating minimization problems\n                      , in Proc. 25th ACM Symposium on the Theory of Computing, 1993, pp. 286\u2013293, 1993.","DOI":"10.1145\/167088.167172"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574005"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970074"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794268753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:21Z","timestamp":1787336061000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794268753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794268753"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794268753","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}