{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:00:37Z","timestamp":1766134837233,"version":"3.48.0"},"reference-count":88,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2121952"],"award-info":[{"award-number":["CCF-2121952"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2237288"],"award-info":[{"award-number":["CCF-2237288"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2517033"],"award-info":[{"award-number":["CCF-2517033"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1991\/19"],"award-info":[{"award-number":["1991\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"DOI":"10.1137\/23m1589670","type":"journal-article","created":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T08:56:58Z","timestamp":1766134618000},"page":"1643-1701","source":"Crossref","is-referenced-by-count":0,"title":["A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8223-9944","authenticated-orcid":true,"given":"Hung","family":"Le","sequence":"first","affiliation":[{"name":"UMass, Amherst, MA USA."}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel."}]}],"member":"351","published-online":{"date-parts":[[2025,12,19]]},"reference":[{"key":"ref1","unstructured":"S. Alstrup, S. Dahlgaard, A. Filtser, M. St\u00f6ckel, and C. Wulff-Nilsen, Constructing light spanners deterministically in near-linear time, in 27th Annual European Symposium on Algorithms (ESA 2019), LIPIcs. Leibniz Int. Proc. Inform. 144, 2019,4."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid, Euclidean spanners: Short, thin, and lanky, in Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC\u201995, ACM, New York, 1995, pp. 489\u2013498.","DOI":"10.1145\/225058.225191"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Communication-time trade-offs in network synchronization, in Proceedings of the 4th Principles of Distributed Computing, ACM, New York, 1985, pp. 272\u2013276.","DOI":"10.1145\/323596.323621"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Baratz, and D. Peleg, Cost-sensitive analysis of communication protocols, in Proceedings of the 9th Principles of Distributed Computing, ACM, New York, 1990, pp. 177\u2013187.","DOI":"10.1145\/93385.93417"},{"key":"ref6","unstructured":"B. Awerbuch, A. Baratz, and D. Peleg, Efficient Broadcast and Light-Weight Spanners, Technical report CS92-22, Weizmann Institute, Rehovot, Israel, 1992\n                      ."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"ref9","first-page":"80","author":"Ben-Or M.","year":"1983","journal-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC\u201983"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"Y. Ben-Shimol, A. Dvir, and M. Segal, SPLAST: A novel approach for multicasting in mobile wireless ad hoc networks, in Proceedings of the IEEE 15th International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC. 2004, Barcelona, IEEE, Piscataway, NJ, 2004, pp. 1011\u20131015, https:\/\/doi.org\/10.1109\/PIMRC.2004.1373851.","DOI":"10.1109\/PIMRC.2004.1373851"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2020.101622"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.76"},{"key":"ref13","first-page":"2371","author":"Borradaile G.","year":"2019","journal-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201819"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9293-4"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58150-3_14"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/OPNARC.2002.1019237"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/2915183"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan, and J. Soares, New sparseness results on graph spanners, in Proceedings of the Eighth Annual Symposium on Computational Geometry, ACM, New York, 1992, pp. 192\u2013201.","DOI":"10.1145\/142675.142717"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355562"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"S. Chechik and C. Wulff-Nilsen, Near-optimal light spanners, in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201916, SIAM, Philadelphia, 2016, 883\u2013892.","DOI":"10.1137\/1.9781611974331.ch63"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00280-8"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"L. P. Chew, There is a planar graph almost as good as the complete graph, in Proceedings of the Second Annual Symposium on Computational Geometry, SCG \u201886, ACM, New York, 1986, pp. 169\u2013177.","DOI":"10.1145\/10515.10534"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, Performance-driven global routing for cell based ICS, in Proceedings of the 9th ICCD, IEEE Computer Society, Los Alamitos, CA, 1991, pp. 170\u2013173.","DOI":"10.1109\/ICCD.1991.139874"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, Provably good algorithms for performance-driven global routing, in Proceedings. of the 5th ISCAS, IEEE, New York, 1992, pp. 2240\u20132243.","DOI":"10.1109\/ISCAS.1992.230514"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/43.137519"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_72"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"G. Das, P. Heffernan, and G. Narasimhan, Optimally sparse spanners in 3-dimensional Euclidean space, in Proceedings of the 9th Annual Symposium on Computational Geometry, SCG\u201993, ACM, New York, 1993, pp. 53\u201362.","DOI":"10.1145\/160985.160998"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000105"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"G. Das and G. Narasimhan, A fast algorithm for constructing sparse Euclidean spanners, in Proceedings of the 10th SoCG, ACM, New York, 1994, pp. 132\u2013139.","DOI":"10.1145\/177424.177579"},{"key":"ref33","unstructured":"G. Das, G. Narasimhan, and J. Salowe, A new way to weigh malnourished Euclidean graphs, in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201995, SIAM, Philadelphia, 1995, pp. 215\u2013222."},{"key":"ref34","unstructured":"A. V. Dejan Kostic, Latency Versus Cost Optimizations in Hierarchical Overlay Networks, Technical report, Duke University, Durham, NC, 2002\n                      ."},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3274651"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"M. Elkin, O. Neiman, and S. Solomon, Light spanners, in Proceedings of the 41st ICALP, Springer, Berlin, 2014, pp. 442\u2013452.","DOI":"10.1007\/978-3-662-43948-7_37"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/2819008"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/2888397"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.12.004"},{"key":"ref42","unstructured":"J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang, Graph distances in the streaming model: The value of space, in Proceedings. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201905, SIAM, Philadelphia, 2005, pp. 745\u2013754."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/18M1210678"},{"key":"ref44","first-page":"174","volume-title":"International Workshop on Approximation and Online Algorithms, WAOA \u201806","author":"F\u00fcrer M.","year":"2006"},{"key":"ref45","first-page":"31","volume":"3","author":"F\u00fcrer M.","year":"2012","journal-title":"J. Comput. Geom."},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2004.837364"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"L. Gottlieb, A light metric spanner, in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, Berkeley, CA, IEEE Computer Society, Los Alamitos, CA, 2015, pp. 759\u2013772, https:\/\/doi.org\/10.1109\/FOCS.2015.52.","DOI":"10.1109\/FOCS.2015.52"},{"key":"ref48","unstructured":"L. Gottlieb and L. Roditty, Improved algorithms for fully dynamic geometric spanners and geometric routing, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201908, SIAM, Philadelphia, 2008, pp. 591\u2013600."},{"key":"ref49","unstructured":"M. Grigni and P. Sissokho, Light spanners and approximate TSP in weighted graphs with forbidden minors, in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201902, SIAM, Philadephia, 2002, pp. 852\u2013857."},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"ref51","volume":"1996","author":"Halperin S.","journal-title":"manuscript"},{"key":"ref52","first-page":"135","author":"Han Y.","year":"2002","journal-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"P. N. Klein, A linear-time approximation scheme for planar weighted TSP, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201905, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 647\u2013657, https:\/\/doi.org\/10.1109\/SFCS.2005.7.","DOI":"10.1109\/SFCS.2005.7"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"P. N. Klein, Subset spanner for planar graphs, with application to subset TSP, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC\u201906, ACM, New York, 2006, pp. 749\u2013756, https:\/\/doi.org\/10.1145\/1132516.1132620.","DOI":"10.1145\/1132516.1132620"},{"key":"ref56","first-page":"37","volume":"38","author":"Kostochka A. V.","year":"1982","journal-title":"Metody Diskret. Analiz."},{"key":"ref57","doi-asserted-by":"crossref","unstructured":"H. Le, A PTAS for subset TSP in minor-free graphs, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, SIAM, Philadelphia, 2020, pp. 2279\u20132298, https:\/\/doi.org\/10.1137\/1.9781611975994.140.","DOI":"10.1137\/1.9781611975994.140"},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"H. Le and S. Solomon, Truly optimal Euclidean spanners, in 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, MD, IEEE Computer Society, Los Alamitos, CA, 2019, pp. 1078\u20131100, https:\/\/doi.org\/10.1109\/FOCS.2019.00069.","DOI":"10.1109\/FOCS.2019.00069"},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"H. Le and S. Solomon, Near-optimal spanners for general graphs in (nearly) linear time, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, SIAM, Philadelphia, 2022, pp. 3332\u20133361.","DOI":"10.1137\/1.9781611977073.132"},{"key":"ref60","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and A. Lingas, There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees, in International Symposium on Optimal Algorithms, Springer, Berlin, 1989, pp. 9\u201313.","DOI":"10.1007\/3-540-51859-2_2"},{"key":"ref61","first-page":"1268","volume":"3","author":"Li X.","year":"2002","journal-title":"Proceedings of 21st Annual Joint Conference of the IEEE Computer and Communications Societies"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1239871"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001366"},{"key":"ref64","first-page":"315","volume":"40","author":"Mare\u0161 M.","year":"2004","journal-title":"Arch. Math."},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1145\/1807048.1807054"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"ref72","unstructured":"L. Perkovic and I. A. Kanj, On geometric spanners of Euclidean and unit disk graphs, in 25th International Symposium on Theoretical Aspects of Computer Science, STACS \u201808, LIPIcs. Leibniz Int. Proc. Inform., Wadern, Germany, 2008, pp. 409\u2013420."},{"key":"ref73","doi-asserted-by":"crossref","unstructured":"S. B. Rao and W. D. Smith, Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC\u201998, ACM, New York, 1998, pp. 540\u2013550, https:\/\/doi.org\/10.1145\/276698.276868.","DOI":"10.1145\/276698.276868"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"ref78","doi-asserted-by":"crossref","unstructured":"J. S. Salowe, Construction of multidimensional spanner graphs, with applications to minimum spanning trees, Proceedings of the 7th Annual Symposium on Computational Geometry, SoCG\u201991, ACM, New York, 1991, pp. 256\u2013261, https:\/\/doi.org\/10.1145\/109648.109677.","DOI":"10.1145\/109648.109677"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2010.2053381"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"ref82","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick, Approximate distance oracles, in Proceedings of the 33rd STOC, ACM, New York, 2001, pp. 183\u2013192.","DOI":"10.1145\/380752.380798"},{"key":"ref83","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick, Compact routing schemes, in Proceedings of the 13th SPAA, ACM, New York, 2001, pp. 1\u201310.","DOI":"10.1145\/378580.378581"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574695"},{"key":"ref85","doi-asserted-by":"crossref","unstructured":"J. Vogel, J. Widmer, D. Farin, M. Mauve, and W. Effelsberg, Priority-based distribution trees for application-level multicast, in Proceedings of the 2nd Workshop on Network and System Support for Games, NETGAMES,  Redwood City, CA, ACM, New York, 2003, pp. 148\u2013157, https:\/\/doi.org\/10.1145\/963900.963914.","DOI":"10.1145\/963900.963914"},{"key":"ref86","doi-asserted-by":"crossref","unstructured":"P. von Rickenbach and R. Wattenhofer, Gathering correlated data in sensor networks, in Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, Philadelphia, PA, ACM, New York, 2004, pp. 60\u201366, https:\/\/doi.org\/10.1145\/1022630.1022640.","DOI":"10.1145\/1022630.1022640"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1002\/dac.844"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1002\/net.10019"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T08:57:06Z","timestamp":1766134626000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1589670"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,19]]},"references-count":88,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/23M1589670"],"URL":"https:\/\/doi.org\/10.1137\/23m1589670","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,19]]}}}