{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:49:40Z","timestamp":1742392180308,"version":"3.28.0"},"reference-count":21,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/ccc.2004.1313826","type":"proceedings-article","created":{"date-parts":[[2004,11,13]],"date-time":"2004-11-13T00:14:14Z","timestamp":1100304854000},"page":"150-160","source":"Crossref","is-referenced-by-count":9,"title":["Tight lower bounds for certain parameterized NP-hard problems"],"prefix":"10.1109","author":[{"family":"Jianer Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Chor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Xiuzhen Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Juedes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Kanj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Ge Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"journal-title":"Algorithms for Building Multiple Sequence Alignments and Evolutionary Trees","year":"2000","author":"roth-korostensky","key":"19"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0058"},{"key":"18","first-page":"269","article-title":"Combinatorial approaches to finding subtle signals in DNA sequences","author":"pevzner","year":"2000","journal-title":"Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology"},{"key":"15","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"nes?etr?il","year":"1985","journal-title":"Commentations Mathematicae Universitatis Carolinae"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"13","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which problems have strongly exponential complexity?","volume":"63","author":"impagliazzo","year":"2001","journal-title":"Journal of Computer and System Sciences"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"11","doi-asserted-by":"crossref","DOI":"10.4086\/cjtcs.1997.001","article-title":"On limited versus polynomial nondeterminism","author":"feige","year":"1997","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(94)90082-5"},{"key":"21","first-page":"185","article-title":"Exact algorithms for NP-hard problems: A survey","volume":"2570","author":"woeginger","year":"2003","journal-title":"Combinatorial Optimization - Eureka! You Shrink! Volume 2570 of Lecture Notes in Computer Science"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00074-6"},{"journal-title":"Resolving Conflicts from Problems in Computational Biology","year":"2000","author":"stege","key":"20"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1089\/10665270252935430"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00034-Z"},{"key":"10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","author":"downey","year":"1999","journal-title":"Parameterized Complexity"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90003-Z"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00075-8"},{"key":"9","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S1571-0661(04)81014-4","article-title":"Cutting up is hard to do: The parameterized complexity of k-cut and related problems","volume":"78","author":"downey","year":"2003","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00081-3"}],"event":{"name":"Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.","location":"Amherst, MA, USA"},"container-title":["Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004."],"original-title":[],"link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/xplorestaging.ieee.org\/ielx5\/9188\/29139\/01313826.pdf?arnumber=1313826","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T11:52:46Z","timestamp":1497613966000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/ieeexplore.ieee.org\/document\/1313826\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":21,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1109\/ccc.2004.1313826","relation":{},"subject":[]}}