{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:52Z","timestamp":1740122392066,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["311892\/2021-3"],"award-info":[{"award-number":["311892\/2021-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2015\/11937-9","2019\/14471-1"],"award-info":[{"award-number":["2015\/11937-9","2019\/14471-1"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2016\/01860-1"],"award-info":[{"award-number":["2016\/01860-1"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["313146\/2022-5"],"award-info":[{"award-number":["313146\/2022-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s10878-024-01197-9","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T11:07:15Z","timestamp":1723028835000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial algorithms for sparse spanners on subcubic graphs"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5759-5418","authenticated-orcid":false,"given":"R.","family":"G\u00f3mez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1067-6421","authenticated-orcid":false,"given":"F. K.","family":"Miyazawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8229-3139","authenticated-orcid":false,"given":"Y.","family":"Wakababayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,7]]},"reference":[{"key":"1197_CR1","doi-asserted-by":"publisher","first-page":"100253","DOI":"10.1016\/j.cosrev.2020.100253","volume":"37","author":"R Ahmed","year":"2020","unstructured":"Ahmed R, Bodwin G, Sahneh F, Hamm K, Latifi M, Kobourov S, Spence R (2020) Graph spanners: a tutorial review. Comput Sci Rev 37:100253","journal-title":"Comput Sci Rev"},{"key":"1197_CR2","doi-asserted-by":"crossref","unstructured":"Ahmed R, Hamm K, Latifi\u00a0Jebelli M, Kobourov S, Sahneh F, Spence R (2019) Approximation algorithms and an integer program for multi-level graph spanners. In: Analysis of experimental algorithms, lecture notes in computer science, vol. 11544, Springer, Cham, pp 541\u2013562","DOI":"10.1007\/978-3-030-34029-2_35"},{"key":"1197_CR3","doi-asserted-by":"crossref","unstructured":"\u00c1lvarez-Miranda E, Sinnl M (2019) Mixed-integer programming approaches for the tree $$t^*$$-spanner problem. Optim Lett 13(7):1693\u20131709","DOI":"10.1007\/s11590-018-1340-0"},{"issue":"4","key":"1197_CR4","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch B (1985) Complexity of network synchronization. J ACM 32(4):804\u2013823","journal-title":"J ACM"},{"issue":"4","key":"1197_CR5","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S Baswana","year":"2006","unstructured":"Baswana S, Sen S (2006) Approximate distance oracles for unweighted graphs in expected $$O(n^2)$$ time. ACM Trans Algorithms 2(4):557\u2013577","journal-title":"ACM Trans Algorithms"},{"issue":"6","key":"1197_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender H (1996) A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J Comput 25(6):1305\u20131317","journal-title":"SIAM J Comput"},{"issue":"1","key":"1197_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00453-006-1209-y","volume":"47","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt A, Dragan F, Le H, Le V, Uehara R (2007) Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47(1):27\u201351","journal-title":"Algorithmica"},{"issue":"2","key":"1197_CR8","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(94)90073-6","volume":"48","author":"L Cai","year":"1994","unstructured":"Cai L (1994) NP-completeness of minimum spanner problems. Discrete Appl Math 48(2):187\u2013194","journal-title":"Discrete Appl Math"},{"issue":"3","key":"1197_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L Cai","year":"1995","unstructured":"Cai L, Corneil D (1995) Tree spanners. SIAM J Discrete Math 8(3):359\u2013387","journal-title":"SIAM J Discrete Math"},{"issue":"4","key":"1197_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/net.3230240406","volume":"24","author":"L Cai","year":"1994","unstructured":"Cai L, Keil M (1994) Spanners in graphs of bounded degree. Networks 24(4):233\u2013249","journal-title":"Networks"},{"key":"1197_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph structure and monadic second-order logic, Encyclopedia of Mathematics and its Applications","author":"B Courcelle","year":"2012","unstructured":"Courcelle B, Engelfriet J (2012) Graph structure and monadic second-order logic, Encyclopedia of Mathematics and its Applications, vol 138. Cambridge University Press, Cambridge"},{"key":"1197_CR12","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.dam.2021.08.010","volume":"304","author":"F Couto","year":"2021","unstructured":"Couto F, Cunha L (2021) Hardness and efficiency on $$t$$-admissibility for graph operations. Discrete Appl Math 304:342\u2013348","journal-title":"Discrete Appl Math"},{"key":"1197_CR13","doi-asserted-by":"crossref","unstructured":"Couto F, Cunha L, Posner D (2021) Edge tree spanners, graphs and combinatorial optimization: from theory to applications: CTW2020 Proceedings. Springer, Cham, pp 195\u2013207","DOI":"10.1007\/978-3-030-63072-0_16"},{"key":"1197_CR14","volume-title":"Linear programming 2: theory and extensions","author":"G Dantzig","year":"2003","unstructured":"Dantzig G, Thapa M (2003) Linear programming 2: theory and extensions. Springer, New York"},{"issue":"6","key":"1197_CR15","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1016\/j.jcss.2010.10.002","volume":"77","author":"F Dragan","year":"2011","unstructured":"Dragan F, Fomin F, Golovach P (2011) Spanners in sparse graphs. J Comput Syst Sci 77(6):1108\u20131119","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"1197_CR16","doi-asserted-by":"publisher","first-page":"884","DOI":"10.1007\/s00453-013-9765-4","volume":"69","author":"F Dragan","year":"2014","unstructured":"Dragan F, K\u00f6hler E (2014) An approximation algorithm for the tree $$t$$-spanner problem on unweighted graphs via generalized chordal graphs. Algorithmica 69(4):884\u2013905","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"1197_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0166-218X(00)00226-2","volume":"108","author":"S Fekete","year":"2001","unstructured":"Fekete S, Kremer J (2001) Tree spanners in planar graphs. Discrete Appl Math 108(1\u20132):85\u2013103","journal-title":"Discrete Appl Math"},{"issue":"3","key":"1197_CR18","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.ipl.2010.10.021","volume":"111","author":"F Fomin","year":"2011","unstructured":"Fomin F, Golovach P, van Leeuwen E (2011) Spanners of bounded degree graphs. Inform Process Lett 111(3):142\u2013144","journal-title":"Inform Process Lett"},{"key":"1197_CR19","doi-asserted-by":"crossref","unstructured":"G\u00f3mez R, Miyazawa FK, Wakabayashi Y (2022) Minimum $$t$$-spanners on subcubic graphs, WALCOM: algorithms and computation. In: Lecture notes in computer science, vol. 13174, Springer, Cham, pp 365\u2013380","DOI":"10.1007\/978-3-030-96731-4_30"},{"key":"1197_CR20","doi-asserted-by":"publisher","first-page":"113691","DOI":"10.1016\/j.tcs.2023.113691","volume":"947","author":"R G\u00f3mez","year":"2023","unstructured":"G\u00f3mez R, Miyazawa FK, Wakabayashi Y (2023) Improved NP-hardness results for the minimum $$t$$-spanner problem on bounded-degree graphs. Theor Comput Sci 947:113691","journal-title":"Theor Comput Sci"},{"key":"1197_CR21","doi-asserted-by":"crossref","unstructured":"G\u00f3mez R, Miyazawa FK, Wakabayashi Y (2022) Tree 3-spanners on generalized prisms of graphs, LATIN, theoretical informatics. In: Lecture notes in computer science, vol. 13568, Springer, Cham, pp 557\u2013573","DOI":"10.1007\/978-3-031-20624-5_34"},{"key":"1197_CR22","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.tcs.2018.06.031","volume":"746","author":"Y Kobayashi","year":"2018","unstructured":"Kobayashi Y (2018) NP-hardness and fixed-parameter tractability of the minimum spanner problem. Theor Comput Sci 746:88\u201397","journal-title":"Theor Comput Sci"},{"key":"1197_CR23","doi-asserted-by":"publisher","first-page":"125502","DOI":"10.1016\/j.amc.2020.125502","volume":"386","author":"L Lin","year":"2020","unstructured":"Lin L, Lin Y (2020) Optimality computation of the minimum stretch spanning tree problem. Appl Math Comput 386:125502","journal-title":"Appl Math Comput"},{"key":"1197_CR24","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.dam.2017.10.025","volume":"236","author":"I Papoutsakis","year":"2018","unstructured":"Papoutsakis I (2018) Tree spanners of bounded degree graphs. Discrete Appl Math 236:395\u2013407","journal-title":"Discrete Appl Math"},{"issue":"1","key":"1197_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg D, Sch\u00e4ffer A (1989) Graph spanners. J Graph Theory 13(1):99\u2013116","journal-title":"J Graph Theory"},{"issue":"4","key":"1197_CR26","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg D, Ullman J (1989) An optimal synchronizer for the hypercube. SIAM J Comput 18(4):740\u2013747","journal-title":"SIAM J Comput"},{"issue":"3","key":"1197_CR27","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg D, Upfal E (1989) A trade-off between space and efficiency for routing tables. J ACM 36(3):510\u2013530","journal-title":"J ACM"},{"issue":"1","key":"1197_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup M, Zwick U (2005) Approximate distance oracles. J ACM 52(1):1\u201324","journal-title":"J ACM"},{"issue":"2","key":"1197_CR29","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1997.2641","volume":"136","author":"G Venkatesan","year":"1997","unstructured":"Venkatesan G, Rotics U, Madanlal M, Makowsky J, Pandu Rangan C (1997) Restrictions of minimum spanner problems. Inform Comput 136(2):143\u2013164","journal-title":"Inform Comput"},{"issue":"11","key":"1197_CR30","doi-asserted-by":"publisher","first-page":"1418","DOI":"10.1177\/0278364915576491","volume":"34","author":"W Wang","year":"2015","unstructured":"Wang W, Balkcom D, Chakrabarti A (2015) A fast online spanner for roadmap construction. Int J Rob Res 34(11):1418\u20131432","journal-title":"Int J Rob Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01197-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01197-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01197-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T19:12:18Z","timestamp":1724440338000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01197-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1197"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01197-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,8]]},"assertion":[{"value":"13 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest. The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"11"}}