{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:53Z","timestamp":1740109313120,"version":"3.37.3"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}]},{"name":"Univerzita Karlova v Praze","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00453-020-00785-5","type":"journal-article","created":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T12:04:20Z","timestamp":1613131460000},"page":"1352-1370","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Travelling on Graphs with Small Highway Dimension"],"prefix":"10.1007","volume":"83","author":[{"given":"Yann","family":"Disser","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[]},{"given":"Max","family":"Klimm","sequence":"additional","affiliation":[]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,12]]},"reference":[{"key":"785_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: Proceedings of 28th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 690\u2013699 (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_58","DOI":"10.1007\/978-3-642-22006-7_58"},{"key":"785_CR2","doi-asserted-by":"publisher","DOI":"10.1145\/2985473","author":"I Abraham","year":"2016","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. J. ACM (2016). https:\/\/doi.org\/10.1145\/2985473","journal-title":"J. ACM"},{"key":"785_CR3","doi-asserted-by":"publisher","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of 21st Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 782\u2013793 (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.64","DOI":"10.1137\/1.9781611973075.64"},{"issue":"5","key":"785_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998). https:\/\/doi.org\/10.1145\/290179.290180","journal-title":"J. ACM"},{"key":"785_CR5","unstructured":"Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of 9th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 33\u201341 (1998)"},{"key":"785_CR6","doi-asserted-by":"publisher","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In: Proceedings of 33rd Annual IEEE Symposium on Foundations Computer Science (FOCS), pp. 14\u201323 (1992). https:\/\/doi.org\/10.1145\/278298.278306","DOI":"10.1145\/278298.278306"},{"key":"785_CR7","doi-asserted-by":"publisher","unstructured":"Bartal, Y., Gottlieb, L.A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings of 44th Annual ACM Symposium on Theory Computing (STOC), pp. 663\u2013672 (2012). https:\/\/doi.org\/10.1145\/2213977.2214038","DOI":"10.1145\/2213977.2214038"},{"key":"785_CR8","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge 74, 175\u2013192 (2009)","DOI":"10.1090\/dimacs\/074\/07"},{"key":"785_CR9","doi-asserted-by":"publisher","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Proceedings of 9th Workshop Algorithm Engineering and Experiments (ALENEX) (2007). https:\/\/doi.org\/10.1137\/1.9781611972870.5","DOI":"10.1137\/1.9781611972870.5"},{"key":"785_CR10","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2027216.2027219","volume":"58","author":"M Bateni","year":"2011","unstructured":"Bateni, M., Hajiaghayi, M.T., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58, 21:1\u201321:37 (2011). https:\/\/doi.org\/10.1145\/2027216.2027219","journal-title":"J. ACM"},{"key":"785_CR11","doi-asserted-by":"publisher","unstructured":"Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for $$k$$-center, $$k$$-median, and capacitated vehicle routing in bounded highway dimension. In: Proceedings of 26th European Symposium Algorithms (ESA), pp. 8:1\u20138:15 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.8","DOI":"10.4230\/LIPIcs.ESA.2018.8"},{"key":"785_CR12","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32, 171\u2013176 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90039-2","journal-title":"Inf. Process. Lett."},{"key":"785_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0167-6377(89)90037-0","volume":"8","author":"R Bland","year":"1989","unstructured":"Bland, R., Shallcross, D.: Large traveling salesman problems arising from experiments in X-ray crystallography: a preliminary report on computation. Oper. Res. Lett. 8, 125\u2013128 (1989). https:\/\/doi.org\/10.1016\/0167-6377(89)90037-0","journal-title":"Oper. Res. Lett."},{"key":"785_CR14","unstructured":"Blum, J.: Hierarchy of transportation network parameters and hardness results (2019). arXiv:1905.11166"},{"key":"785_CR15","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008","journal-title":"Inf. Comput."},{"key":"785_CR16","doi-asserted-by":"publisher","unstructured":"Bornd\u00f6rfer, R., Neumann, M., Pfetsch, M.E.: The line connectivity problem. In: Fleischmann, B., Borgwardt, K.H., Klein, R., Tuma, A.: (eds.) Operations Research Proceedings, pp. 557\u2013562 (2009). https:\/\/doi.org\/10.1007\/978-3-642-00142-0_90","DOI":"10.1007\/978-3-642-00142-0_90"},{"key":"785_CR17","doi-asserted-by":"publisher","unstructured":"Borradaile, G., Kenyon-Mathieu, C., Klein, P.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1285\u20131294 (2007). https:\/\/doi.org\/10.1145\/1541885.1541892","DOI":"10.1145\/1541885.1541892"},{"key":"785_CR18","doi-asserted-by":"publisher","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: An improved LP-based approximation for Steiner tree. In: Proceedings of the 42nd Annual ACM Symposium on Theory Computing (STOC), pp. 583\u2013592 (2010). https:\/\/doi.org\/10.1145\/1806689.1806769","DOI":"10.1145\/1806689.1806769"},{"key":"785_CR19","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1109\/TPAMI.2016.2564404","volume":"39","author":"CY Chen","year":"2018","unstructured":"Chen, C.Y., Grauman, K.: Efficient activity detection in untrimmed video with max-subgraph search. IEEE Trans. Pattern Anal. Mach. Intell. 39, 908\u2013921 (2018). https:\/\/doi.org\/10.1109\/TPAMI.2016.2564404","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"785_CR20","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci. 406, 207\u2013214 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.06.046","journal-title":"Theor. Comput. Sci."},{"key":"785_CR21","doi-asserted-by":"publisher","first-page":"i189","DOI":"10.1093\/bioinformatics\/btt205","volume":"29","author":"SA Chowdhury","year":"2013","unstructured":"Chowdhury, S.A., Shackney, S.E., Heselmeyer-Haddad, K., Ried, T., Sch\u00e4ffer, A.A., Schwartz, R.: Phylogenetic analysis of multiprobe fluorescence in situ hybridization data from tumor cell populations. Bioinformatics 29, i189\u2013i198 (2013). https:\/\/doi.org\/10.1093\/bioinformatics\/btt205","journal-title":"Bioinformatics"},{"key":"785_CR22","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976). http:\/\/www.dtic.mil\/dtic\/tr\/fulltext\/u2\/a025602.pdf"},{"key":"785_CR23","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 5th edn. Springer, Berlin (2017)","edition":"5"},{"key":"785_CR24","doi-asserted-by":"crossref","unstructured":"Disser, Y., Feldmann, A.E., Klimm, M., K\u00f6nemann, J.: Travelling on graphs with small highway dimension. In: Proceedings of the\u00a045th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019, pp. 175\u2013189 (2019)","DOI":"10.1007\/978-3-030-30786-8_14"},{"key":"785_CR25","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1007\/s00453-018-0455-0","volume":"81","author":"AE Feldmann","year":"2019","unstructured":"Feldmann, A.E.: Fixed parameter approximations for $$k$$-center problems in low highway dimension graphs. Algorithmica 81, 1031\u20131052 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0455-0","journal-title":"Algorithmica"},{"key":"785_CR26","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/16M1067196","volume":"41","author":"AE Feldmann","year":"2018","unstructured":"Feldmann, A.E., Fung, W.S., K\u00f6nemann, J., Post, I.: A $$(1+\\varepsilon )$$-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J. Comput. 41, 1667\u20131704 (2018). https:\/\/doi.org\/10.1137\/16M1067196","journal-title":"SIAM J. Comput."},{"key":"785_CR27","doi-asserted-by":"publisher","unstructured":"Feldmann, A.E., Marx, D.: The parameterized hardness of the $$k$$-center problem in transportation networks. In: Proceedings of 16th Scandinavian Symposium and Workshop Algorithm Theory (SWAT), pp. 19:1\u201319:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.19","DOI":"10.4230\/LIPIcs.SWAT.2018.19"},{"key":"785_CR28","unstructured":"Feldmann, A.E., Saulpic, D.: Polynomial time approximation schemes for clustering in low highway dimension graphs. In: Proceedings of the 28th European Symposium on Algorithms (ESA), vol. 173, pp. 46:1\u201346:22 (2020). arXiv:2006.12897"},{"key":"785_CR29","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math 32, 835\u2013859 (1977). https:\/\/doi.org\/10.1137\/0132072","journal-title":"SIAM J. Appl. Math"},{"key":"785_CR30","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977). https:\/\/doi.org\/10.1137\/0132071","journal-title":"SIAM J. Appl. Math."},{"key":"785_CR31","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman vol. 29, (2002)"},{"key":"785_CR32","doi-asserted-by":"publisher","unstructured":"Grigni, M., E. Koutsoupias, Papadimitriou, C.H.: An approximation scheme for planar graph TSP. In: Proceedings of 36th Annual IEEE Symposium on Foundations Computer Science (FOCS), pp. 640\u2013645 (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492665","DOI":"10.1109\/SFCS.1995.492665"},{"key":"785_CR33","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel, M., Holland, O.: Solution of large-scale symmetric travelling salesman problems. Math. Program. 51, 141\u2013202 (1991). https:\/\/doi.org\/10.1007\/BF01586932","journal-title":"Math. Program."},{"key":"785_CR34","first-page":"33","volume-title":"Combinatorial Optimization: Methods and Applications","author":"S Held","year":"2011","unstructured":"Held, S., Korte, B., Rautenbach, D., Vygen, J.: Combinatorial optimization in VLSI design. In: Chvatal, V. (ed.) Combinatorial Optimization: Methods and Applications, pp. 33\u201396. IOS Press, Amsterdam (2011)"},{"issue":"3","key":"785_CR35","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533\u2013550 (1986). https:\/\/doi.org\/10.1145\/5925.5933","journal-title":"J. ACM"},{"key":"785_CR36","unstructured":"Hougardy, S., Pr\u00f6mel, H.J.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: Proceedings of 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 448\u2013453 (1999)"},{"key":"785_CR37","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) improved approximation algorithm for metric TSP. arXiv:2007.01409 (2020)","DOI":"10.1145\/3406325.3451009"},{"key":"785_CR38","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"785_CR39","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81, 1665\u20131677 (2015). https:\/\/doi.org\/10.1016\/j.jcss.2015.06.003","journal-title":"J. Comput. Syst. Sci."},{"key":"785_CR40","doi-asserted-by":"publisher","unstructured":"Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for $$(k, r)$$-center. In: Proceedings of 28th International Symposium on Algorithms Computing (ISAAC), pp. 50:1\u201350:13 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2017.50","DOI":"10.4230\/LIPIcs.ISAAC.2017.50"},{"issue":"6","key":"785_CR41","doi-asserted-by":"publisher","first-page":"1926","DOI":"10.1137\/060649562","volume":"37","author":"P Klein","year":"2008","unstructured":"Klein, P.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926\u20131952 (2008). https:\/\/doi.org\/10.1137\/060649562","journal-title":"SIAM J. Comput."},{"key":"785_CR42","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Viennot, L.: Beyond highway dimension: small distance labels using tree skeletons. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1462\u20131478 (2017)","DOI":"10.1137\/1.9781611974782.95"},{"key":"785_CR43","doi-asserted-by":"publisher","unstructured":"Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: Proceedings of 47th Annual IEEE Symposium on Foundations Computing Science (FOCS), pp. 119\u2013132 (2006). https:\/\/doi.org\/10.1109\/FOCS.2006.9","DOI":"10.1109\/FOCS.2006.9"},{"key":"785_CR44","doi-asserted-by":"publisher","first-page":"217","DOI":"10.4086\/toc.2014.v010a009","volume":"10","author":"M Lampis","year":"2014","unstructured":"Lampis, M.: Improved inapproximability for TSP. Theory Comput. 10, 217\u2013236 (2014). https:\/\/doi.org\/10.4086\/toc.2014.v010a009","journal-title":"Theory Comput."},{"key":"785_CR45","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1287\/opre.33.5.1050","volume":"33","author":"G Laporte","year":"1985","unstructured":"Laporte, G., Nobert, Y., Desrochers, M.: Optimal routing under capacity and distance restrictions. Oper. Res. 33, 1050\u20131073 (1985). https:\/\/doi.org\/10.1287\/opre.33.5.1050","journal-title":"Oper. Res."},{"key":"785_CR46","doi-asserted-by":"publisher","first-page":"717","DOI":"10.2307\/3008306","volume":"26","author":"JK Lenstra","year":"1975","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G.: Some simple applications of the traveling salesman problem. Oper. Res. Quart. 26, 717\u201333 (1975). https:\/\/doi.org\/10.2307\/3008306","journal-title":"Oper. Res. Quart."},{"key":"785_CR47","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-005-0660-x","volume":"105","author":"I Ljubi\u0107","year":"2006","unstructured":"Ljubi\u0107, I., Weiskirchner, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Program. 105, 427\u2013449 (2006). https:\/\/doi.org\/10.1007\/s10107-005-0660-x","journal-title":"Math. Program."},{"key":"785_CR48","doi-asserted-by":"publisher","unstructured":"Loboda, A.A., Artyomov, M.N., Sergushichev, A.A.: Solving generalized maximum-weight connected subgraph problem for network enrichment analysis. In: Proceedings of the 16th Workshop Algorithms in Bioinformatics (WABI), pp. 210\u2013221 (2016). https:\/\/doi.org\/10.1007\/978-3-319-43681-4_17","DOI":"10.1007\/978-3-319-43681-4_17"},{"issue":"4","key":"785_CR49","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, $$k$$-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999). https:\/\/doi.org\/10.1137\/S0097539796309764","journal-title":"SIAM J. Comput."},{"key":"785_CR50","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theor. Comput. Sci. 4, 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"785_CR51","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s00493-006-0008-z","volume":"26","author":"CH Papadimitriou","year":"2006","unstructured":"Papadimitriou, C.H., Vempala, S.: On the approximability of the traveling salesman problem. Combinatorica 26, 101\u2013120 (2006). https:\/\/doi.org\/10.1007\/s00493-006-0008-z","journal-title":"Combinatorica"},{"key":"785_CR52","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122\u2013134 (2005). https:\/\/doi.org\/10.1137\/S0895480101393155","journal-title":"SIAM J. Discrete Math."},{"key":"785_CR53","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2960-3","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: $$7\/5$$-approximation for the graph-TSP, $$3\/2$$ for the path version, and $$4\/3$$ for two-edge-connected subgraphs. Combinatorica (2014). https:\/\/doi.org\/10.1007\/s00493-011-2960-3","journal-title":"Combinatorica"},{"key":"785_CR54","doi-asserted-by":"publisher","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 281\u2013290 (2004). https:\/\/doi.org\/10.1145\/1007352.1007399","DOI":"10.1145\/1007352.1007399"},{"key":"785_CR55","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1137\/S0097539799352735","volume":"30","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and Steiner tree. SIAM J. Comput. 30, 475\u2013485 (2000). https:\/\/doi.org\/10.1137\/S0097539799352735","journal-title":"SIAM J. Comput."},{"key":"785_CR56","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00785-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00785-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00785-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:13:56Z","timestamp":1671236036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00785-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,12]]},"references-count":56,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["785"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00785-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,2,12]]},"assertion":[{"value":"3 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}