{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:11:27Z","timestamp":1725567087642},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_98","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:34:13Z","timestamp":1127813653000},"page":"975-984","source":"Crossref","is-referenced-by-count":8,"title":["W-Hardness Under Linear FPT-Reductions: Structural Properties and Further Applications"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiuzhen","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"98_CR1","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On fixed parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences\u00a054, 465\u2013474 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"98_CR2","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0304-3975(01)00343-7","volume":"289","author":"L. Cai","year":"2002","unstructured":"Cai, L., Juedes, D., Kanj, I.A.: Inapproximability of non NP-hard optimization problems. Theoretical Computer Science\u00a0289, 553\u2013571 (2002)","journal-title":"Theoretical Computer Science"},{"key":"98_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Information Processing Letters\u00a064, 165\u2013171 (1997)","journal-title":"Information Processing Letters"},{"key":"#cr-split#-98_CR4.1","doi-asserted-by":"crossref","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. In: Proc. 19th Annual IEEE Conference on Computational Complexity (CCC 2004), pp. 150???160 (2004);","DOI":"10.1109\/CCC.2004.1313826"},{"key":"#cr-split#-98_CR4.2","unstructured":"Journal version is to appear in Information and Computation"},{"key":"98_CR5","doi-asserted-by":"crossref","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Linear FPT reductions and computational lower bounds. In: Proc. 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 212\u2013221 (2004)","DOI":"10.1145\/1007352.1007391"},{"key":"98_CR6","doi-asserted-by":"crossref","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: W-hardness under linear FPTreductions: structural properties and further applications, Tech. Report, Dept. Computer Science, Texas A&M University (2005)","DOI":"10.1007\/11533719_98"},{"key":"98_CR7","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"98_CR8","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, Heidelberg (1999)"},{"key":"98_CR9","doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M.: Model-checking problems as a basis for parameterized intractability. In: Proc. 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pp. 388\u2013397 (2004)","DOI":"10.1109\/LICS.2004.1319633"},{"key":"98_CR10","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The parameterized complexity of database queries. In: Proc. 20th ACM Symposium on Principles of Database Systems (PODS 2001), pp. 82\u201392 (2001)","DOI":"10.1145\/375551.375564"},{"key":"98_CR11","unstructured":"Huang, X.: Parameterized Complexity and Polynomial-time Approximation Schemes, Ph.D. Dissertation, Department of Computer Science, Texas A&M University (December 2004)"},{"key":"98_CR12","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences\u00a063, 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"98_CR13","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1995","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Pub., Reading (1995)"},{"key":"98_CR14","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"98_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"C.H. Papadimitriou","year":"1996","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of VC dimension. Journal of Computer and System Sciences\u00a053, 161\u2013170 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"98_CR16","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C.H. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. Journal of Computer and System Sciences\u00a058, 407\u2013427 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"98_CR17","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences\u00a067, 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_98","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T18:37:49Z","timestamp":1586457469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_98"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11533719_98","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}