{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:25:22Z","timestamp":1742383522993},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797227"},{"type":"electronic","value":"9783540797234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79723-4_12","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T10:22:17Z","timestamp":1210069337000},"page":"115-128","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Complexity and Approximability of the SLCS Problem"],"prefix":"10.1007","author":[{"given":"Sylvain","family":"Guillemot","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"12_CR1","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(1), 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"issue":"1\u20132","key":"12_CR2","first-page":"31","volume":"147","author":"H.L. Bodlaender","year":"1994","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(1\u20132), 31\u201354 (1994)","journal-title":"Theoretical Computer Science"},{"key":"12_CR3","first-page":"449","volume-title":"Proc. STOC 1994","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: Proc. STOC 1994, pp. 449\u2013458. ACM, New York (1994)"},{"issue":"1","key":"12_CR4","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.: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science\u00a0244(1), 167\u2013188 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"4\u20135","key":"12_CR5","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Archive for Mathematical Logic\u00a036(4\u20135), 321\u2013337 (1997)","journal-title":"Archive for Mathematical Logic"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem. In: Proc. STOC 2008 (to appear, 2008)","DOI":"10.1145\/1374376.1374404"},{"key":"12_CR7","doi-asserted-by":"crossref","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":"12_CR8","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank Aggregation Methods for the Web. In: WWW10 (2001)","DOI":"10.1145\/371920.372165"},{"key":"12_CR9","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation revisited (2001)"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica\u00a020, 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: Proc. ACM SIGMOD 2003, pp. 301\u2013312 (2003)","DOI":"10.1145\/872757.872795"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0196-6774(03)00081-6","volume":"49","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R., Hallett, M.T., Stege, U.: Analogs & duals of the MAST problem for sequences & trees. Journal of Algorithms\u00a049(1), 192\u2013216 (2003)","journal-title":"Journal of Algorithms"},{"key":"12_CR13","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"12_CR14","unstructured":"Halld\u00f3rsson, M.M.: Approximation via Partitioning. Technical Report IS-RR-95-0003F, School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku (1995)"},{"key":"12_CR15","unstructured":"Hallett, M.T.: An integrated complexity analysis of problems from computational biology. PhD thesis, Department of Computer Science, University of Victoria, Victoria, B.C., Canada (1996)"},{"key":"12_CR16","unstructured":"Hodge, J., Klima, R.E.: The Mathematics of Voting and Elections: A Hands-On Approach. In: Mathematical World, vol.\u00a022. AMS (2000)"},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"key":"12_CR18","volume-title":"Mathematics of phylogeny and evolution","author":"B.M.E. Moret","year":"2004","unstructured":"Moret, B.M.E., Tang, J., Warnow, T.: Reconstructing phylogenies from gene-content and gene-order data. In: Gascuel, O. (ed.) Mathematics of phylogeny and evolution. Oxford University Press, Oxford (2004)"},{"key":"12_CR19","doi-asserted-by":"crossref","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 University Press, Oxford (2006)"},{"issue":"4","key":"12_CR20","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(4), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica\u00a015, 281\u2013288 (1995)","journal-title":"Combinatorica"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/3-540-44674-5_26","volume-title":"Implementation and Application of Automata","author":"H.T. Wareham","year":"2001","unstructured":"Wareham, H.T.: The parameterized complexity of intersection and composition operations on sets of finite-state automata. In: Yu, S., P\u0103un, A. (eds.) CIAA 2000. LNCS, vol.\u00a02088, pp. 302\u2013310. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79723-4_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:29:58Z","timestamp":1619522998000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79723-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797227","9783540797234"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79723-4_12","relation":{},"subject":[]}}