{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:31:11Z","timestamp":1725543071509},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_16","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T13:41:33Z","timestamp":1155649293000},"page":"136-145","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds and Parameterized Approach for Longest Common Subsequence"],"prefix":"10.1007","author":[{"given":"Xiuzhen","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","volume-title":"Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties. Springer, New York (1999)"},{"key":"16_CR2","first-page":"49","volume":"11","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hallett, M.T., Wareham, H.T.: Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences\u00a011, 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science\u00a0147, 31\u201354 (1995)","journal-title":"Theoretical Computer Science"},{"key":"16_CR4","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":"16_CR5","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":"16_CR6","first-page":"481","volume":"8","author":"K.M. Chao","year":"1992","unstructured":"Chao, K.M., Pearson, W.R., Miller, W.: Aligning two sequences within a specific diagonal band. Computer Applications in the Biosciences\u00a08, 481\u2013487 (1992)","journal-title":"Computer Applications in the Biosciences"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J. Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I., Xia, G.: Tight lower bounds for parameterized NP-hard problems. Information and Computation\u00a0201, 216\u2013231 (2005)","journal-title":"Information and Computation"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Linear FPT reductions and computational lower bounds. In: Proc. of the 36th ACM Symposium on Theory of Computing, pp. 212\u2013221 (2004)","DOI":"10.1145\/1007352.1007391"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1007\/11533719_98","volume-title":"Computing and Combinatorics","author":"J. Chen","year":"2005","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: W-hardness linear FPT-reductions: structural properties and further applications. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 975\u2013984. Springer, Heidelberg (2005)"},{"key":"16_CR10","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., Jia, W.: Vertex Cover: Further observations and further improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"16_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1007\/3-540-45465-9_63","volume-title":"Automata, Languages and Programming","author":"X. Deng","year":"2002","unstructured":"Deng, X., Li, G., Li, Z., Ma, B., Wang, L.: A PTAS for distinguishing (sub)string selection. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 740\u2013751. Springer, Heidelberg (2002)"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539701397825","volume":"32","author":"X. Deng","year":"2003","unstructured":"Deng, X., Li, G., Li, Z., Ma, B., Wang, L.: Genetic design of drugs without side-effects. SIAM Journal on Computing\u00a032, 1073\u20131090 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prieto, E., Rosamond, F.A.: Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems. Electr. Notes Theor. Comput. Sci.\u00a078 (2003)","DOI":"10.1016\/S1571-0661(04)81014-4"},{"key":"16_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-45841-7_21","volume-title":"STACS 2002","author":"M. Fellows","year":"2002","unstructured":"Fellows, M., Gramm, J., Niedermeier, R.: Parameterized intractability of motif search problems. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 262\u2013273. Springer, Heidelberg (2002)"},{"key":"16_CR17","unstructured":"Hallett, M.: An Integrated Complexity Analysi of Problems for Computational Biology, Ph.D. Thesis, University of Victoria (1996)"},{"key":"16_CR18","unstructured":"Huang, X.: Parameterized Complexity and Polynomial-time Approximation Schemes, Ph.D. Dissertation, Texas A&M University (2004)"},{"key":"16_CR19","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., Zane, F.: 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":"16_CR20","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequence and longest common subsequences. SIAM Journal on Computing\u00a024, 1112\u20131139 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. Journal of the ACM\u00a049, 157\u2013171 (2002)","journal-title":"Journal of the ACM"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., 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":"16_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"C. Papadimitriou","year":"1996","unstructured":"Papadimitriou, C., 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":"16_CR24","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C., 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":"16_CR25","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"},{"key":"16_CR26","unstructured":"Sze, S.-H.: Lectures notes of Special Topics in Computational Biology, Texas A & M University (2002)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:13:39Z","timestamp":1605644019000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11809678_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}