{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:40:04Z","timestamp":1748461204374,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_38","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"469-480","source":"Crossref","is-referenced-by-count":5,"title":["A $$(1+{\\varepsilon })$$ ( 1 + \u03b5 ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs"],"prefix":"10.1007","author":[{"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[]},{"given":"Wai Shing","family":"Fung","sequence":"additional","affiliation":[]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[]},{"given":"Ian","family":"Post","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms, pp. 782\u2013793 (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"38_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/978-3-642-22006-7_58","volume-title":"Automata, Languages and Programming","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 690\u2013699. Springer, Heidelberg (2011)"},{"key":"38_CR3","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient shortest path algorithms. Technical Report (2013)"},{"key":"38_CR4","unstructured":"Ageev, A.A.: An approximation scheme for the uncapacitated facility location problem on planar graphs"},{"key":"38_CR5","unstructured":"Ageev, A.A.: A criterion of polynomial-time solvability for the network location problem. In: Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization, pp. 237\u2013245 (1992)"},{"issue":"5","key":"38_CR6","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)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"38_CR7","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","volume":"97","author":"S Arora","year":"2003","unstructured":"Arora, S.: Approximation schemes for np-hard geometric optimization problems: A survey. Math. Programming 97(1\u20132), 43\u201369 (2003)","journal-title":"Math. Programming"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for euclidean k-medians and related problems. In: Proceedings, ACM Symp. on Theory of Computing, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. In: Proceedings, ACM Symp. on Theory of Computing, pp. 2\u201311 (1996)","DOI":"10.1109\/SFCS.1996.548458"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings, ACM Symp. on Theory of Computing, pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings, ACM Symp. on Theory of Computing, pp. 663\u2013672 (2012)","DOI":"10.1145\/2213977.2214038"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Algorithm Engineering & Experiments. SIAM (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"38_CR13","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1090\/dimacs\/074\/07","volume":"74","author":"H Bast","year":"2009","unstructured":"Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. The Shortest Path Problem: Ninth DIMACS Implementation Challenge 74, 175\u2013192 (2009)","journal-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M.T., Korula, N., Marx, D.: Prize-collecting steiner problems on planar graphs. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms, pp. 1028\u20131049 (2011)","DOI":"10.1137\/1.9781611973082.79"},{"key":"38_CR15","unstructured":"Borradaile, G., Kenyon-Mathieu, C., Klein, P.: A polynomial-time approximation scheme for steiner tree in planar graphs. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms, pp. 1285\u20131294 (2007)"},{"key":"38_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/3-540-45471-3_18","volume-title":"Algorithm Theory - SWAT 2002","author":"M Chleb\u00edk","year":"2002","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of the steiner tree problem on graphs. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 170\u2013179. Springer, Heidelberg (2002)"},{"key":"38_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-48224-5_17","volume-title":"Automata, Languages and Programming","author":"L Engebretsen","year":"2001","unstructured":"Engebretsen, L., Karpinski, M.: Approximation hardness of TSP with bounded metrics. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 201\u2013212. Springer, Heidelberg (2001)"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings, ACM Symp. on Theory of Computing, pp. 448\u2013455. ACM (2003)","DOI":"10.1145\/780542.780608"},{"issue":"1","key":"38_CR19","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings, IEEE Symposium on Foundations of Computer Science, pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"6","key":"38_CR21","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 Journal on Computing 37(6), 1926\u20131952 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"38_CR22","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 Journal on Computing 28(4), 1298\u20131309 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"38_CR23","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. ii. algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"38_CR24","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings, ACM Symp. on Theory of Computing, pp. 281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"},{"key":"38_CR25","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag, New York (2001). Inc"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:10:09Z","timestamp":1748459409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}