{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004212,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":84,"publisher":"ACM","funder":[{"name":"National Science Foundation","award":["CCF-2443017,CCF-2237288,CCF-2121952"],"award-info":[{"award-number":["CCF-2443017,CCF-2237288,CCF-2121952"]}]},{"name":"Google Research","award":[""],"award-info":[{"award-number":[""]}]},{"name":"European Research Council","award":["101043159"],"award-info":[{"award-number":["101043159"]}]},{"name":"United States - Israel Binational Science Foundation","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718312","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"2257-2268","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6714-7988","authenticated-orcid":false,"given":"Hsien-Chih","family":"Chang","sequence":"first","affiliation":[{"name":"Dartmouth College, Hanover, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8487-9682","authenticated-orcid":false,"given":"Jonathan","family":"Conroy","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8223-9944","authenticated-orcid":false,"given":"Hung","family":"Le","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst, Amherst, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2254-5100","authenticated-orcid":false,"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7350-331X","authenticated-orcid":false,"given":"Cuong","family":"Than","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst, Amherst, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.62"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371039"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835743"},{"key":"e_1_3_2_1_4_1","volume-title":"Routing in Networks with Low Doubling Dimension. In the 26th IEEE International Conference on Distributed Computing Systems (ICDCS \u201806)","author":"Abraham Ittai","year":"2006","unstructured":"Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. 2006. Routing in Networks with Low Doubling Dimension. In the 26th IEEE International Conference on Distributed Computing Systems (ICDCS \u201806). 75."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_32"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007916"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1115575"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519977"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225191"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.328973"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89571"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2022.06.001"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.66"},{"key":"e_1_3_2_1_16_1","volume-title":"Richard Tan, and Dimitrios M Thilikos.","author":"Bodlaender Hans L","year":"1997","unstructured":"Hans L Bodlaender, Jan Van Leeuwen, Richard Tan, and Dimitrios M Thilikos. 1997. On interval routing schemes and treewidth. information and computation, 139, 1 (1997), 92\u2013109."},{"volume-title":"An Alternate Proof of Near-Optimal Light Spanners","author":"Bodwin Greg","key":"e_1_3_2_1_17_1","unstructured":"Greg Bodwin. 2024. An Alternate Proof of Near-Optimal Light Spanners. Society for Industrial and Applied Mathematics, 39\u201355."},{"key":"e_1_3_2_1_18_1","unstructured":"Greg Bodwin and Jeremy Flics. 2024. A Lower Bound for Light Spanners in General Graphs. arxiv:2406.04459. arxiv:2406.04459"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.76"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.145"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972863.12"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00012"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.45"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Tsz-Hong Chan Hubert","year":"2005","unstructured":"Hubert Tsz-Hong Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. 2005. On hierarchical routing in doubling metrics. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005. SIAM, 762\u2013771. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070540"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142717"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00139"},{"key":"e_1_3_2_1_28_1","volume-title":"Optimal Euclidean Tree Covers. In 40th International Symposium on Computational Geometry (SoCG","author":"Chang Hsien-Chih","year":"2024","unstructured":"Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovi\u0107, Shay Solomon, and Cuong Than. 2024. Optimal Euclidean Tree Covers. In 40th International Symposium on Computational Geometry (SoCG 2024). See also the full version arXiv:2403.17754"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.191"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484268"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch63"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.42"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04355-0_41"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390180"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28402"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.160998"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201995)","author":"Das Gautam","year":"1995","unstructured":"Gautam Das, Giri Narasimhan, and Jeffrey Salowe. 1995. A new way to weigh Malnourished Euclidean graphs. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201995). 215\u2013222."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing. 11\u201320","author":"Eilam Tamar","year":"1998","unstructured":"Tamar Eilam, Cyril Gavoille, and David Peleg. 1998. Compact routing schemes with low stretch factor. In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing. 11\u201320."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/140979538"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.07.038"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2888397"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00141"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00683-w"},{"key":"e_1_3_2_1_47_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Filtser Arnold","year":"2019","unstructured":"Arnold Filtser. 2019. On Strong Diameter Padded Decompositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019)."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2024.56"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520042"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1210678"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_62"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45841-7_4"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762113"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989526"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347148"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.52"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545492"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.2001.959889"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0308-2"},{"key":"e_1_3_2_1_61_1","volume-title":"First Passage Percolation with Queried Hints. In International Conference on Artificial Intelligence and Statistics (AISTATS","author":"Karntikoon Kritkorn","year":"2024","unstructured":"Kritkorn Karntikoon, Yiheng Shen, Sreenivas Gollapudi, Kostas Kollias, Aaron Schild, and Ali Kemal Sinop. 2024. First Passage Percolation with Queried Hints. In International Conference on Artificial Intelligence and Statistics (AISTATS 2024). 238, 4231\u20134239."},{"key":"e_1_3_2_1_62_1","volume-title":"No. 318 on SWAT 88: 1st Scandinavian Workshop on Algorithm Theory","author":"Keil J. M.","year":"1948","unstructured":"J. M. Keil. 1988. Approximating the complete Euclidean graph. In No. 318 on SWAT 88: 1st Scandinavian Workshop on Algorithm Theory. Springer-Verlag, Berlin, Heidelberg. 208\u2013213. isbn:3540194878"},{"key":"e_1_3_2_1_63_1","volume-title":"Gutwin","author":"Mark Keil J.","year":"1992","unstructured":"J. Mark Keil and Carl A. Gutwin. 1992. Classes of graphs which approximate the complete euclidean graph. Discrete Comput. Geom., 7, 1 (1992), dec, 13\u201328. issn:0179-5376"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146412"},{"key":"e_1_3_2_1_65_1","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"Konjevod Goran","year":"2007","unstructured":"Goran Konjevod, Andr\u00e9a W. Richa, and Donglin Xia. 2007. Optimal scale-free compact routing schemes in networks of low doubling dimension. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 939\u2013948. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283484"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_26"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281113"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993879"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/941079.941089"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","unstructured":"Hung Le and Shay Solomon. 2022. Truly Optimal Euclidean Spanners. SIAM J. Comput. FOCS19\u2013135\u2013FOCS19\u2013199. https:\/\/doi.org\/10.1137\/20M1317906 10.1137\/20M1317906","DOI":"10.1137\/20M1317906"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585185"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00013"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00044"},{"key":"e_1_3_2_1_76_1","volume-title":"Path-Reporting Distance Oracles with Linear Size. In 19th Scandinavian Symposium on Algorithm Theory.","author":"Neiman Ofer","year":"2024","unstructured":"Ofer Neiman and Idan Shabat. 2024. Path-Reporting Distance Oracles with Linear Size. In 19th Scandinavian Symposium on Algorithm Theory."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.29"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073823"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/30.4.298"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627856"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.015"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:50:36Z","timestamp":1750693836000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":84,"alternative-id":["10.1145\/3717823.3718312","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718312","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}