{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:28Z","timestamp":1750694788148,"version":"3.37.3"},"reference-count":75,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T00:00:00Z","timestamp":1656374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T00:00:00Z","timestamp":1656374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Israel science foundation","award":["1817\/17"],"award-info":[{"award-number":["1817\/17"]}]},{"name":"United States-Israel binational science foundation","award":["2015813"],"award-info":[{"award-number":["2015813"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00453-022-00994-0","type":"journal-article","created":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T20:18:59Z","timestamp":1656447539000},"page":"2987-3007","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Light Spanners for High Dimensional Norms via Stochastic Decompositions"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-9304","authenticated-orcid":false,"given":"Arnold","family":"Filtser","sequence":"first","affiliation":[]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,28]]},"reference":[{"issue":"6","key":"994_CR1","doi-asserted-by":"publisher","first-page":"3026","DOI":"10.1016\/j.aim.2011.08.003","volume":"228","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. Adv. Math. 228(6), 3026\u20133126 (2011)","journal-title":"Adv. Math."},{"key":"994_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Baratz, A.\u00a0E., Peleg, D.: Cost-sensitive analysis of communication protocols. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, Quebec City, Quebec, Canada, August 22-24, 1990, pp 177\u2013187, (1990)","DOI":"10.1145\/93385.93417"},{"key":"994_CR3","unstructured":"Awerbuch, B., Baratz, A.\u00a0E., Peleg, D.: Efficient broadcast and light-weight spanners. Manuscript, (1991)"},{"key":"994_CR4","doi-asserted-by":"publisher","first-page":"100253","DOI":"10.1016\/j.cosrev.2020.100253","volume":"37","author":"AR Ahmed","year":"2020","unstructured":"Ahmed, A.R., Bodwin, G., Sahneh, F.D., Hamm, K., Jebelli, M.J.L., Kobourov, S.G., Spence, R.: Graph spanners: A tutorial review. Comput. Sci. Rev. 37, 100253 (2020)","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"994_CR5","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/3371039","volume":"16","author":"I Abraham","year":"2020","unstructured":"Abraham, I., Chechik, S., Elkin, M., Filtser, A., Neiman, O.: Ramsey spanning trees and their applications. ACM Trans. Algorithms 16(2), 19:1-19:21 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"994_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"994_CR7","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1137\/17M1112406","volume":"48","author":"I Abraham","year":"2019","unstructured":"Abraham, I., Gavoille, C., Gupta, A., Neiman, O., Talwar, K.: Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM J. Comput. 48(3), 1120\u20131145 (2019)","journal-title":"SIAM J. Comput."},{"key":"994_CR8","doi-asserted-by":"crossref","unstructured":"Ahn, K.\u00a0J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In Michael Benedikt, Markus Kr\u00f6tzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pp 5\u201314. ACM, (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"994_CR9","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp 459\u2013468, (2006)","DOI":"10.1109\/FOCS.2006.49"},{"key":"994_CR10","doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Communication-time trade-offs in network synchronization. In Proc. of 4th PODC, pp 272\u2013276, (1985)","DOI":"10.1145\/323596.323621"},{"issue":"4","key":"994_CR11","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804\u2013823 (1985)","journal-title":"J. ACM"},{"key":"994_CR12","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In Proc. of 37th FOCS, pp 184\u2013193, (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"994_CR13","doi-asserted-by":"crossref","unstructured":"Biswas, A.\u00a0S., Dory, M., Ghaffari, M., Mitrovic, S., Nazari, Y.: Massively parallel algorithms for distance approximation and spanners. In Kunal Agrawal and Yossi Azar, editors, SPAA \u201921: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pp 118\u2013128. ACM, (2021)","DOI":"10.1145\/3409964.3461784"},{"key":"994_CR14","unstructured":"Bhore, S., Filtser, A., Khodabandeh, H., T\u00f3th, C.\u00a0D.: Online spanners in metric spaces. CoRR, arXiv:2202.09991, (2022)"},{"key":"994_CR15","unstructured":"Braynard, R., Kostic, D., Rodriguez, A., Chase, J., Vahdat, A.: Opus: an overlay peer utility service. In Prof. of 5th OPENARCH, (2002)"},{"issue":"3","key":"994_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1706591.1706593","volume":"57","author":"P Biswal","year":"2010","unstructured":"Biswal, P., Lee, J.R., Rao, S.: Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM 57(3), 1\u201323 (2010)","journal-title":"J. ACM"},{"key":"994_CR17","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Le, H., Wulff-Nilsen, C.: Minor-free graphs have light spanners. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 767\u2013778, (2017)","DOI":"10.1109\/FOCS.2017.76"},{"key":"994_CR18","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Le, H., Wulff-Nilsen, C.: Greedy spanners are optimal in doubling metrics. In Timothy\u00a0M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp 2371\u20132379. SIAM, (2019)","DOI":"10.1137\/1.9781611975482.145"},{"key":"994_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Int. J. Comput. Geometry Appl. 5, 125\u2013144 (1995)","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"2","key":"994_CR20","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1137\/050630696","volume":"20","author":"D Coppersmith","year":"2006","unstructured":"Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math. 20(2), 463\u2013501 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"994_CR21","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Filtser, A., Klein, P.\u00a0N., Le, H.: On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp 589\u2013600. IEEE, (2020)","DOI":"10.1109\/FOCS46700.2020.00061"},{"key":"994_CR22","doi-asserted-by":"crossref","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multi-dimensional point-sets with applications to $$k$$-nearest-neighbors and $$n$$-body potential fields. In Proc. of 24th STOC, pages 546\u2013556, (1992)","DOI":"10.1145\/129712.129766"},{"issue":"2","key":"994_CR23","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/S0097539701395978","volume":"34","author":"G Calinescu","year":"2005","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: Approximation algorithms for the 0-extension problem. SIAM J. Comput. 34(2), 358\u2013372 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"994_CR24","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28(1), 210\u2013236 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"994_CR25","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/3199607","volume":"14","author":"S Chechik","year":"2018","unstructured":"Chechik, S., Wulff-Nilsen, C.: Near-optimal light spanners. ACM Trans. Algorithms 14(3), 33:1-33:15 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"994_CR26","doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P.\u00a0J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional euclidean space. In Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, CA, USA, May 19-21, 1993, pages 53\u201362, (1993)","DOI":"10.1145\/160985.160998"},{"key":"994_CR27","unstructured":"Kostic, D., Vahdat, A.: Latency versus cost optimizations in hierarchical overlay networks. Technical report, Duke University, (CS-2001-04), (2002)"},{"key":"994_CR28","unstructured":"Elkin, M., Filtser, A., Neiman, O.: Distributed construction of light networks. In Yuval Emek and Christian Cachin, editors, PODC \u201920: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pp 483\u2013492. ACM, (2020)"},{"issue":"2","key":"994_CR29","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms 1(2), 283\u2013323 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"994_CR30","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O., Solomon, S.: Light spanners. In Proc. of 41th ICALP, pp 442\u2013452, (2014)","DOI":"10.1007\/978-3-662-43948-7_37"},{"issue":"5","key":"994_CR31","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00446-005-0147-2","volume":"18","author":"M Elkin","year":"2006","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. Distributed Computing 18(5), 375\u2013385 (2006)","journal-title":"Distributed Computing"},{"key":"994_CR32","unstructured":"Filtser, A.: On strong diameter padded decompositions. In Dimitris Achlioptas and L\u00e1szl\u00f3\u00a0A. V\u00e9gh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs, pages 6:1\u20136:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019)"},{"key":"994_CR33","doi-asserted-by":"crossref","unstructured":"Filtser, A.: Hop-constrained metric embeddings and their applications. In 62st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, February 7-10, 2022, pages 492\u2013503. IEEE, (2021)","DOI":"10.1109\/FOCS52979.2021.00056"},{"key":"994_CR34","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In Proc. of 16th SODA, pp 745\u2013754, (2005)"},{"key":"994_CR35","doi-asserted-by":"crossref","unstructured":"Filtser, A., Kapralov, M., Nouri, N.: Graph spanners by sketching in dynamic streams and the simultaneous communication model. In D\u00e1niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 1894\u20131913. SIAM, (2021)","DOI":"10.1137\/1.9781611976465.113"},{"key":"994_CR36","doi-asserted-by":"crossref","unstructured":"Filtser, A., Le, H.: Clan embeddings into trees, and low treewidth graphs. In Samir Khuller and Virginia\u00a0Vassilevska Williams, editors, STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 342\u2013355. ACM, (2021)","DOI":"10.1145\/3406325.3451043"},{"key":"994_CR37","unstructured":"Filtser, A., Neiman, O.: Light spanners for high dimensional norms via stochastic decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 29:1\u201329:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2018)"},{"key":"994_CR38","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, STOC \u201903, pages 448\u2013455, New York, NY, USA, (2003). ACM","DOI":"10.1145\/780542.780608"},{"issue":"3","key":"994_CR39","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1002\/rsa.10036","volume":"20","author":"U Feige","year":"2002","unstructured":"Feige, U., Schechtman, G.: On the optimality of the random hyperplane rounding technique for max cut. Random Struct. Algorithms 20(3), 403\u2013440 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"994_CR40","doi-asserted-by":"crossref","unstructured":"Filtser, A., Solomon, S.: The greedy spanner is existentially optimal. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pp. 9\u201317, (2016)","DOI":"10.1145\/2933057.2933114"},{"key":"994_CR41","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of 44th FOCS, pages 534\u2013543, (2003)"},{"key":"994_CR42","doi-asserted-by":"crossref","unstructured":"Gottlieb, L.A.: A light metric spanner. In: Proceedings of 56th FOCS, pp 759\u2013772, (2015)","DOI":"10.1109\/FOCS.2015.52"},{"key":"994_CR43","doi-asserted-by":"crossref","unstructured":"Grigni, M.: Approximate TSP in graphs with forbidden minors. In: Proceedings of 27th ICALP, pp 869\u2013877, (2000)","DOI":"10.1007\/3-540-45022-X_73"},{"key":"994_CR44","volume-title":"Topological Graph Theory","author":"JL Gross","year":"1987","unstructured":"Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley-Interscience, New York, NY, USA (1987)"},{"key":"994_CR45","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Indyk, P., Sidiropoulos, A.: Euclidean spanners in high dimensions. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp 804\u2013809, (2013)","DOI":"10.1137\/1.9781611973105.57"},{"issue":"5","key":"994_CR46","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"994_CR47","unstructured":"Klein, P.\u00a0N.: A subset spanner for planar graphs, : with application to subset TSP. In Jon\u00a0M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 749\u2013756. ACM, (2006)"},{"key":"994_CR48","unstructured":"Krauthgamer, R., Lee, J.\u00a0R., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp 434\u2013443, Washington, DC, USA, (2004). IEEE Computer Society"},{"key":"994_CR49","doi-asserted-by":"crossref","unstructured":"Kelner, J.\u00a0A., Lee, J.\u00a0R., Price, G.\u00a0N., Teng, S.-H.: Higher eigenvalues of graphs. In FOCS, pp 735\u2013744, (2009)","DOI":"10.1109\/FOCS.2009.69"},{"key":"994_CR50","doi-asserted-by":"crossref","unstructured":"Klein, P.\u00a0N., Plotkin, S.\u00a0A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In STOC, pp 682\u2013690, (1993)","DOI":"10.1145\/167088.167261"},{"issue":"2","key":"994_CR51","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"994_CR52","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00222-004-0400-5","volume":"160","author":"JR Lee","year":"2005","unstructured":"Lee, J.R., Naor, A.: Extending lipschitz functions via random metric partitions. Invent. Math. 160(1), 59\u201395 (2005)","journal-title":"Invent. Math."},{"key":"994_CR53","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 787\u2013832 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"994_CR54","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13(4), 441\u2013454 (1993). (Preliminary version in 2nd SODA, 1991)","journal-title":"Combinatorica"},{"key":"994_CR55","doi-asserted-by":"crossref","unstructured":"Lee, J.\u00a0R., Sidiropoulos, A.: Genus and the geometry of the cut graph. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp 193\u2013201, (2010)","DOI":"10.1137\/1.9781611973075.18"},{"key":"994_CR56","doi-asserted-by":"crossref","unstructured":"Le, H., Solomon, S.: Truly optimal euclidean spanners. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1078\u20131100. IEEE Computer Society, (2019)","DOI":"10.1109\/FOCS.2019.00069"},{"issue":"2","key":"994_CR57","doi-asserted-by":"publisher","first-page":"253","DOI":"10.4171\/JEMS\/79","volume":"9","author":"M Mendel","year":"2007","unstructured":"Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9(2), 253\u2013275 (2007)","journal-title":"J. Eur. Math. Soc."},{"key":"994_CR58","unstructured":"Nguyen, H.L.: Approximate nearest neighbor search in $$\\ell _p$$. CoRR, arXiv:1306.3601, (2013)"},{"key":"994_CR59","doi-asserted-by":"crossref","unstructured":"Narasimhan, G., Smid, Michiel H.M.: Geometric spanner networks. Cambridge University Press, (2007)","DOI":"10.1017\/CBO9780511546884"},{"key":"994_CR60","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In Graph-Theoretic Concepts in Computer Science, 25th International Workshop, WG \u201999, Ascona, Switzerland, June 17-19, 1999, Proceedings, pp 30\u201341, (1999)","DOI":"10.1007\/3-540-46784-X_5"},{"key":"994_CR61","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA (2000)"},{"key":"994_CR62","unstructured":"Parter, M., Rubinfeld, R., Vakilian, A., Yodpinyanee, A.: Local computation algorithms for spanners. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pp 58:1\u201358:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019)"},{"issue":"4","key":"994_CR63","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"994_CR64","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"994_CR65","doi-asserted-by":"crossref","unstructured":"Rao, S.B.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In SOCG, pp 300\u2013306, (1999)","DOI":"10.1145\/304893.304983"},{"key":"994_CR66","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, pp 261\u2013272, (2005)","DOI":"10.1007\/11523468_22"},{"key":"994_CR67","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In Proc. of 32nd ESA, pp 580\u2013591, (2004)","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"994_CR68","doi-asserted-by":"crossref","unstructured":"Salowe, J.S.: Construction of multidimensional spanner graphs, with applications to minimum spanning trees. In: Proceedings of 7th SoCG, pp 256\u2013261, (1991)","DOI":"10.1145\/109648.109677"},{"key":"994_CR69","doi-asserted-by":"crossref","unstructured":"Smid, Michiel H.M.: The weak gap property in metric spaces of bounded doubling dimension. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pp 275\u2013289, (2009)","DOI":"10.1007\/978-3-642-03456-5_19"},{"key":"994_CR70","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp 281\u2013290, (2004)"},{"key":"994_CR71","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of 13th SPAA, pp 1\u201310, (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"994_CR72","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"994_CR73","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"PM Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in $$k$$ dimensions. Discrete Comput. Geom. 6, 369\u2013381 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"994_CR74","doi-asserted-by":"crossref","unstructured":"Vogel, J., Widmer, J., Farin, D., Mauve, M., Effelsberg, W.: Priority-based distribution trees for application-level multicast. In Proceedings of the 2nd Workshop on Network and System Support for Games, NETGAMES 2003, Redwood City, California, USA, May 22-23, 2003, pp 148\u2013157, (2003)","DOI":"10.1145\/963900.963914"},{"issue":"3","key":"994_CR75","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1002\/net.10019","volume":"39","author":"BY Wu","year":"2002","unstructured":"Wu, B.Y., Chao, K.-M., Tang, C.Y.: Light graphs with small routing cost. Networks 39(3), 130\u2013138 (2002)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00994-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00994-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00994-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,28]],"date-time":"2024-09-28T00:03:42Z","timestamp":1727481822000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00994-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,28]]},"references-count":75,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["994"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00994-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,6,28]]},"assertion":[{"value":"17 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}