{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T07:09:56Z","timestamp":1742800196803},"reference-count":21,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2015,2,1]],"date-time":"2015-02-01T00:00:00Z","timestamp":1422748800000},"content-version":"vor","delay-in-days":1461,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Optimization"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1016\/j.disopt.2010.08.003","type":"journal-article","created":{"date-parts":[[2010,12,25]],"date-time":"2010-12-25T05:24:58Z","timestamp":1293254698000},"page":"50-60","source":"Crossref","is-referenced-by-count":13,"title":["Parameterized complexity and approximability of the Longest Compatible Sequence problem"],"prefix":"10.1016","volume":"8","author":[{"given":"S.","family":"Guillemot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/j.disopt.2010.08.003_br000005","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","article-title":"The complexity of some problems on subsequences and supersequences","volume":"25","author":"Maier","year":"1978","journal-title":"Journal of the ACM"},{"key":"10.1016\/j.disopt.2010.08.003_br000010","series-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"10.1016\/j.disopt.2010.08.003_br000015","series-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier","year":"2006"},{"key":"10.1016\/j.disopt.2010.08.003_br000020","series-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"issue":"1","key":"10.1016\/j.disopt.2010.08.003_br000025","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/S0196-6774(03)00081-6","article-title":"Analogs & duals of the MAST problem for sequences & trees","volume":"49","author":"Fellows","year":"2003","journal-title":"Journal of Algorithms"},{"key":"10.1016\/j.disopt.2010.08.003_br000030","series-title":"Mathematics of Phylogeny and Evolution","article-title":"Reconstructing phylogenies from gene-content and gene-order data","author":"Moret","year":"2004"},{"key":"10.1016\/j.disopt.2010.08.003_br000035","series-title":"The Mathematics of Voting and Elections: A Hands-on Approach","volume":"vol. 22","author":"Hodge","year":"2000"},{"key":"10.1016\/j.disopt.2010.08.003_br000040","doi-asserted-by":"crossref","unstructured":"C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation methods for the web, in: WWW10, 2001.","DOI":"10.1145\/371920.372165"},{"key":"10.1016\/j.disopt.2010.08.003_br000045","unstructured":"C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation revisited, 2001."},{"key":"10.1016\/j.disopt.2010.08.003_br000050","doi-asserted-by":"crossref","unstructured":"R. Fagin, R. Kumar, D. Sivakumar, Efficient similarity search and classification via rank aggregation, in: Proc. ACM SIGMOD\u201903, 2003, pp. 301\u2013312.","DOI":"10.1145\/872794.872795"},{"key":"10.1016\/j.disopt.2010.08.003_br000055","series-title":"Proc. STOC\u201994","first-page":"449","article-title":"Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)","author":"Bodlaender","year":"1994"},{"issue":"1","key":"10.1016\/j.disopt.2010.08.003_br000060","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","article-title":"The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs","volume":"244","author":"Bodlaender","year":"2000","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"10.1016\/j.disopt.2010.08.003_br000065","first-page":"49","article-title":"Parameterized complexity analysis in computational biology","volume":"11","author":"Bodlaender","year":"1995","journal-title":"Computer Applications in the Biosciences"},{"issue":"1\u20132","key":"10.1016\/j.disopt.2010.08.003_br000070","first-page":"31","article-title":"The parameterized complexity of sequence alignment and consensus","volume":"147","author":"Bodlaender","year":"1994","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.disopt.2010.08.003_br000075","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","article-title":"Packing directed circuits fractionally","volume":"15","author":"Seymour","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/j.disopt.2010.08.003_br000080","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009191","article-title":"Approximating minimum feedback sets and multicuts in directed graphs","volume":"20","author":"Even","year":"1998","journal-title":"Algorithmica"},{"key":"10.1016\/j.disopt.2010.08.003_br000085","doi-asserted-by":"crossref","unstructured":"J. Chen, Y. Liu, S. Lu, B. O\u2019Sullivan, I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, in: Proc. STOC\u201908, 2008, pp. 177\u2013186.","DOI":"10.1145\/1374376.1374404"},{"issue":"4\u20135","key":"10.1016\/j.disopt.2010.08.003_br000090","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s001530050069","article-title":"On the parameterized complexity of short computation and factorization","volume":"36","author":"Cai","year":"1997","journal-title":"Archive for Mathematical Logic"},{"issue":"4","key":"10.1016\/j.disopt.2010.08.003_br000095","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","article-title":"On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems","volume":"67","author":"Pietrzak","year":"2003","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/j.disopt.2010.08.003_br000100","series-title":"Proc. ICIAA\u201900","first-page":"302","article-title":"The parameterized complexity of intersection and composition operations on sets of finite-state automata","volume":"vol. 2088","author":"Wareham","year":"2000"},{"key":"10.1016\/j.disopt.2010.08.003_br000105","unstructured":"M.T. Hallett, An integrated complexity analysis of problems from computational biology, Ph.D. Thesis, Department of Computer Science, University of Victoria, Victoria, BC, Canada, 1996."}],"container-title":["Discrete Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S1572528610000575?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S1572528610000575?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T05:10:00Z","timestamp":1559884200000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S1572528610000575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["S1572528610000575"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.disopt.2010.08.003","relation":{},"ISSN":["1572-5286"],"issn-type":[{"value":"1572-5286","type":"print"}],"subject":[],"published":{"date-parts":[[2011,2]]}}}