{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:26:38Z","timestamp":1743117998262,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031159138"},{"type":"electronic","value":"9783031159145"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15914-5_32","type":"book-chapter","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:14:22Z","timestamp":1664536462000},"page":"439-452","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimum Weight Euclidean $$(1+\\varepsilon )$$-Spanners"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,1]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","unstructured":"Abu-Affash, A.K., Bar-On, G., Carmi, P.: $$\\delta $$-greedy $$t$$-spanner. Comput. Geom. 100, 101807 (2022). https:\/\/doi.org\/10.1016\/j.comgeo.2021.101807","DOI":"10.1016\/j.comgeo.2021.101807"},{"key":"32_CR2","unstructured":"Agarwal, P.K.: Range searching. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, chap. 40, 3 edn., pp. 1057\u20131092. CRC Press, Boca Raton (2017)"},{"key":"32_CR3","unstructured":"Agarwal, P.K., Wang, Y., Yin, P.: Lower bound for sparse Euclidean spanners. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 670\u2013671 (2005). https:\/\/dl.acm.org\/citation.cfm?id=1070432.1070525"},{"issue":"1","key":"32_CR4","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., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81\u2013100 (1993). https:\/\/doi.org\/10.1007\/BF02189308","journal-title":"Discrete Comput. Geom."},{"key":"32_CR5","doi-asserted-by":"publisher","unstructured":"Bhore, S., T\u00f3th, C.D.: Light euclidean steiner spanners in the plane. In: Proceedings of the 37th Annual Symposium on Computational Geometry (SoCG). LIPIcs, vol. 189, pp. 15:1\u201315:17. Schloss Dagstuhl (2021). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2021.15","DOI":"10.4230\/LIPIcs.SoCG.2021.15"},{"key":"32_CR6","doi-asserted-by":"publisher","unstructured":"Borradaile, G., Le, H., Wulff-Nilsen, C.: Greedy spanners are optimal in doubling metrics. In: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2371\u20132379 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.145","DOI":"10.1137\/1.9781611975482.145"},{"issue":"4","key":"32_CR7","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1007\/s00454-020-00228-6","volume":"64","author":"K Buchin","year":"2020","unstructured":"Buchin, K., Har-Peled, S., Ol\u00e1h, D.: A spanner for the day after. Discrete Comput. Geom. 64(4), 1167\u20131191 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00228-6","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"32_CR8","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/19M1246493","volume":"49","author":"TM Chan","year":"2020","unstructured":"Chan, T.M., Har-Peled, S., Jones, M.: On locality-sensitive orderings and their applications. SIAM J. Comput. 49(3), 583\u2013600 (2020). https:\/\/doi.org\/10.1137\/19M1246493","journal-title":"SIAM J. Comput."},{"key":"32_CR9","doi-asserted-by":"publisher","unstructured":"Das, G., Heffernan, P.J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional euclidean space. In: Proceedings of the 9th Symposium on Computational Geometry (SoCG), pp. 53\u201362 (1993). https:\/\/doi.org\/10.1145\/160985.160998","DOI":"10.1145\/160985.160998"},{"key":"32_CR10","unstructured":"Das, G., Narasimhan, G., Salowe, J.S.: A new way to weigh malnourished euclidean graphs. In: Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 215\u2013222 (1995). https:\/\/dl.acm.org\/citation.cfm?id=313651.313697"},{"issue":"4","key":"32_CR11","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/s00454-009-9230-y","volume":"43","author":"Y Dinitz","year":"2009","unstructured":"Dinitz, Y., Elkin, M., Solomon, S.: Low-light trees, and tight lower bounds for\u00a0euclidean spanners. Discrete Comput. Geom. 43(4), 736\u2013783 (2009). https:\/\/doi.org\/10.1007\/s00454-009-9230-y","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"32_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.5802\/jtnb.255","volume":"11","author":"F Dress","year":"1999","unstructured":"Dress, F.: Discr\u00e9pance des suites de farey. J. Th\u00e9or. Nombres Bordeaux 11(2), 345\u2013367 (1999)","journal-title":"J. Th\u00e9or. Nombres Bordeaux"},{"issue":"5","key":"32_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2819008","volume":"62","author":"M Elkin","year":"2015","unstructured":"Elkin, M., Solomon, S.: Optimal euclidean spanners: really short, thin, and lanky. J. ACM 62(5), 1\u201345 (2015). https:\/\/doi.org\/10.1145\/2819008","journal-title":"J. ACM"},{"issue":"2","key":"32_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1112\/S0025579300000784","volume":"2","author":"L Few","year":"1955","unstructured":"Few, L.: The shortest path and the shortest road through $$n$$ points. Mathematika 2(2), 141\u2013144 (1955). https:\/\/doi.org\/10.1112\/S0025579300000784","journal-title":"Mathematika"},{"issue":"2","key":"32_CR15","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/18M1210678","volume":"49","author":"A Filtser","year":"2020","unstructured":"Filtser, A., Solomon, S.: The greedy spanner is existentially optimal. SIAM J. Comput. 49(2), 429\u2013447 (2020). https:\/\/doi.org\/10.1137\/18M1210678","journal-title":"SIAM J. Comput."},{"key":"32_CR16","first-page":"198","volume":"1924","author":"J Franel","year":"1924","unstructured":"Franel, J.: Les suites de farey et les problemes des nombres premiers. Gottinger Nachr. 1924, 198\u2013201 (1924)","journal-title":"Gottinger Nachr."},{"issue":"1\u20132","key":"32_CR17","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.comgeo.2005.10.001","volume":"35","author":"J Gao","year":"2006","unstructured":"Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. Comput. Geom. 35(1\u20132), 2\u201319 (2006). https:\/\/doi.org\/10.1016\/j.comgeo.2005.10.001","journal-title":"Comput. Geom."},{"key":"32_CR18","doi-asserted-by":"publisher","unstructured":"Gottlieb, L.: A light metric spanner. In: Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 759\u2013772 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.52","DOI":"10.1109\/FOCS.2015.52"},{"issue":"5","key":"32_CR19","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479\u20131500 (2002). https:\/\/doi.org\/10.1137\/S0097539700382947","journal-title":"SIAM J. Comput."},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematics Surveys and Monographs, vol. 173. AMS (2011)","DOI":"10.1090\/surv\/173"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1006\/jnth.1996.0145","volume":"61","author":"P Kargaev","year":"1996","unstructured":"Kargaev, P., Zhigljavsky, A.: Approximation of real numbers by rationals: some metric theorems. J. Number Theor. 61, 209\u2013225 (1996). https:\/\/doi.org\/10.1006\/jnth.1996.0145","journal-title":"J. Number Theor."},{"key":"32_CR22","unstructured":"Landau, E.: Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel. G\u00f6ttinger Nachr. 8, 202\u2013206 (1924). Coll. works, (Thales Verlag, Essen)"},{"key":"32_CR23","doi-asserted-by":"publisher","unstructured":"Le, H., Solomon, S.: Truly optimal Euclidean spanners. In: Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1078\u20131100. IEEE Computer Society (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00069","DOI":"10.1109\/FOCS.2019.00069"},{"key":"32_CR24","doi-asserted-by":"publisher","unstructured":"Le, H., Solomon, S.: Light euclidean spanners with steiner points. In: Proceedins of the 28th European Symposium on Algorithms (ESA). LIPIcs, vol. 173, pp. 67:1\u201367:22. Schloss Dagstuhl (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.67","DOI":"10.4230\/LIPIcs.ESA.2020.67"},{"key":"32_CR25","unstructured":"Le, H., Solomon, S.: Towards a unified theory of light spanners I: fast (yet optimal) constructions. CoRR abs\/2106.15596 (2021). https:\/\/arxiv.org\/abs\/2106.15596"},{"issue":"2","key":"32_CR26","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s10474-018-0868-x","volume":"156","author":"AH Ledoan","year":"2018","unstructured":"Ledoan, A.H.: The discrepancy of farey series. Acta Math. Hungar. 156(2), 465\u2013480 (2018). https:\/\/doi.org\/10.1007\/s10474-018-0868-x","journal-title":"Acta Math. Hungar."},{"issue":"1","key":"32_CR27","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"C Levcopoulos","year":"2002","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.H.M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32(1), 144\u2013156 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0075-x","journal-title":"Algorithmica"},{"key":"32_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.H.M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007). https:\/\/doi.org\/10.1017\/CBO9780511546884"},{"key":"32_CR29","doi-asserted-by":"publisher","unstructured":"Rao, S., Smith, W.D.: Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC), pp. 540\u2013550 (1998). https:\/\/doi.org\/10.1145\/276698.276868","DOI":"10.1145\/276698.276868"},{"issue":"3\u20134","key":"32_CR30","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1007\/s00453-011-9504-7","volume":"62","author":"L Roditty","year":"2012","unstructured":"Roditty, L.: Fully dynamic geometric spanners. Algorithmica 62(3\u20134), 1073\u20131087 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9504-7","journal-title":"Algorithmica"},{"key":"32_CR31","unstructured":"Ruppert, J., Seidel, R.: Approximating the $$d$$-dimensional complete euclidean graph. In: Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG), pp. 207\u2013210 (1991). https:\/\/cccg.ca\/proceedings\/1991\/paper50.pdf"},{"issue":"3","key":"32_CR32","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1137\/120901295","volume":"28","author":"S Solomon","year":"2014","unstructured":"Solomon, S., Elkin, M.: Balancing degree, diameter, and weight in euclidean spanners. SIAM J. Discret. Math. 28(3), 1173\u20131198 (2014). https:\/\/doi.org\/10.1137\/120901295","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"32_CR33","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1137\/0218019","volume":"18","author":"JM Steele","year":"1989","unstructured":"Steele, J.M., Snyder, T.L.: Worst-case growth rates of some classical problems of combinatorial optimization. SIAM J. Comput. 18(2), 278\u2013287 (1989). https:\/\/doi.org\/10.1137\/0218019","journal-title":"SIAM J. Comput."},{"issue":"1","key":"32_CR34","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0212009","volume":"12","author":"KJ Supowit","year":"1983","unstructured":"Supowit, K.J., Reingold, E.M., Plaisted, D.A.: The travelling salesman problem and minimum matching in the unit square. SIAM J. Comput. 12(1), 144\u2013156 (1983). https:\/\/doi.org\/10.1137\/0212009","journal-title":"SIAM J. Comput."},{"key":"32_CR35","unstructured":"T\u00f3th, C.D.: Minimum weight euclidean $$(1+\\varepsilon )$$-spanners. CoRR abs\/2206.14911 (2022). https:\/\/arxiv.org\/abs\/2206.14911"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15914-5_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:20:02Z","timestamp":1664536802000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15914-5_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159138","9783031159145"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15914-5_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcbingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.inf.uni-tuebingen.de\/wg2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"96","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}