{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:21:09Z","timestamp":1758270069963,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_47","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"588-600","source":"Crossref","is-referenced-by-count":5,"title":["Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs"],"prefix":"10.1007","author":[{"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"47_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: SODA, pp. 782\u2013793 (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"47_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":"47_CR3","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient shortest path algorithms. Techical Report (2013)"},{"issue":"2","key":"47_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33(2), 201\u2013226 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"47_CR5","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"47_CR6","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: ALENEX (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"47_CR7","first-page":"175","volume":"74","author":"H Bast","year":"2009","unstructured":"Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. 9th DIMACS Implementation. Challenge 74, 175\u2013192 (2009)","journal-title":"Challenge"},{"key":"47_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-39206-1_9","volume-title":"Automata, Languages, and Programming","author":"R Bauer","year":"2013","unstructured":"Bauer, R., Columbus, T., Rutter, I., Wagner, D.: Search-Space size in contraction hierarchies. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 93\u2013104. Springer, Heidelberg (2013)"},{"key":"47_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-319-03898-8_6","volume-title":"Parameterized and Exact Computation","author":"E Bonnet","year":"2013","unstructured":"Bonnet, E., Escoffier, B., Kim, E.J., Paschos, V.T.: On subexponential and FPT-time inapproximability. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 54\u201365. Springer, Heidelberg (2013)"},{"issue":"11","key":"47_CR10","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation 206(11), 1264\u20131275 (2008)","journal-title":"Information and Computation"},{"issue":"1","key":"47_CR11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. TALG 1(1), 33\u201347 (2005)","journal-title":"TALG"},{"key":"47_CR12","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity, vol. 4. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: STOC, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"47_CR14","doi-asserted-by":"crossref","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. In: ICALP (2015)","DOI":"10.1007\/978-3-662-47672-7_38"},{"key":"47_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-10217-2_2","volume-title":"Combinatorial Algorithms","author":"M Fellows","year":"2009","unstructured":"Fellows, M.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Fiala, J., Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol. 5874, pp. 2\u201310. Springer, Heidelberg (2009)"},{"key":"47_CR16","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS, pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"47_CR17","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: STOC, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"issue":"3","key":"47_CR18","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. JACM 33(3), 533\u2013550 (1986)","journal-title":"JACM"},{"issue":"3","key":"47_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W-L Hsu","year":"1979","unstructured":"Hsu, W.-L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discrete Applied Mathematics 1(3), 209\u2013215 (1979)","journal-title":"Discrete Applied Mathematics"},{"key":"47_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1007\/978-3-662-43948-7_64","volume-title":"Automata, Languages, and Programming","author":"M Lampis","year":"2014","unstructured":"Lampis, M.: Parameterized approximation schemes using graph widths. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 775\u2013786. Springer, Heidelberg (2014)"},{"issue":"1","key":"47_CR21","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal 51(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"issue":"6","key":"47_CR22","first-page":"445","volume":"25","author":"J Plesn\u00edk","year":"1980","unstructured":"Plesn\u00edk, J.: On the computational complexity of centers locating in a graph. Aplikace Matematiky 25(6), 445\u2013452 (1980)","journal-title":"Aplikace Matematiky"},{"key":"47_CR23","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag New York Inc. (2001); ISBN 3-540-65367-8"}],"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-47666-6_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:03:47Z","timestamp":1748459027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}