{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:49:07Z","timestamp":1743072547037,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_39","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T08:37:10Z","timestamp":1246696630000},"page":"463-474","source":"Crossref","is-referenced-by-count":6,"title":["Distortion Is Fixed Parameter Tractable"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Losievskaja","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/1060590.1060624","volume-title":"Proceedings of the STOC","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the line. In: Proceedings of the STOC, pp. 225\u2013233. ACM Press, New York (2005)"},{"key":"39_CR2","first-page":"119","volume-title":"Proceedings of the SODA","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., R\u00e4cke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: Proceedings of the SODA, pp. 119\u2013128. SIAM, Philadelphia (2005)"},{"key":"39_CR3","first-page":"512","volume-title":"Proceedings of the SODA","author":"M. Badoiu","year":"2007","unstructured":"Badoiu, M., Indyk, P., Sidiropoulos, A.: Approximation algorithms for embedding general metrics into trees. In: Proceedings of the SODA, pp. 512\u2013521. SIAM, Philadelphia (2007)"},{"key":"39_CR4","first-page":"449","volume-title":"Proceedings of the STOC","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for problems of bounded width: Hardness for the w hierarchy (extended abstract). In: Proceedings of the STOC, pp. 449\u2013458. ACM Press, New York (1994)"},{"issue":"1-2","key":"39_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","volume":"244","author":"H.L. Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T., Wareham, T., Warnow, T.: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theor. Comput. Sci.\u00a0244(1-2), 167\u2013188 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1999)"},{"key":"39_CR7","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"issue":"2","key":"39_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and l $_{\\mbox{1}}$ -embeddings of graphs. Combinatorica\u00a024(2), 233\u2013269 (2004)","journal-title":"Combinatorica"},{"key":"39_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/11538462_10","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Hall","year":"2005","unstructured":"Hall, A., Papadimitriou, C.H.: Approximating the distortion. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 111\u2013122. Springer, Heidelberg (2005)"},{"key":"39_CR10","first-page":"10","volume-title":"Proceedings of the FOCS","author":"P. Indyk","year":"2001","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Proceedings of the FOCS, pp. 10\u201333. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"39_CR11","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1145\/1007352.1007398","volume-title":"Proceedings of the STOC","author":"C. Kenyon","year":"2004","unstructured":"Kenyon, C., Rabani, Y., Sinclair, A.: Low distortion maps between point sets. In: Proceedings of the STOC, pp. 272\u2013280. ACM Press, New York (2004)"},{"key":"39_CR12","first-page":"573","volume-title":"Proceedings of the International Congress of Mathematicians","author":"N. Linial","year":"2002","unstructured":"Linial, N.: Finite metric-spaces\u2014combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians, vol.\u00a0III, pp. 573\u2013586. Higher Ed. Press, Beijing (2002)"},{"key":"39_CR13","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"issue":"4","key":"39_CR14","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1137\/0601042","volume":"1","author":"J.B. Saxe","year":"1980","unstructured":"Saxe, J.B.: Dynamic programming algorithms for recognizing small bandwidth graphs in polynomial time. SIAM J. on Algebraic and Discrete Methods\u00a01(4), 363\u2013369 (1980)","journal-title":"SIAM J. on Algebraic and Discrete Methods"}],"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-642-02927-1_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T22:02:01Z","timestamp":1685052121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}