{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:39:09Z","timestamp":1767915549822,"version":"3.49.0"},"reference-count":45,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,29]],"date-time":"2013-07-29T00:00:00Z","timestamp":1375056000000},"content-version":"vor","delay-in-days":4227,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[2002,1]]},"DOI":"10.1016\/s1571-0661(04)00301-9","type":"journal-article","created":{"date-parts":[[2004,2,5]],"date-time":"2004-02-05T05:34:35Z","timestamp":1075959275000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["Parameterized Complexity"],"prefix":"10.1016","volume":"61","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","article-title":"\u201cFixed Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogs,\u201d","volume":"73","author":"Abrahamson","year":"1995","journal-title":"Annals of Pure and Applied Logic"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB2","doi-asserted-by":"crossref","unstructured":"J. Alber, H. Fernau and R. Niedermeier, \u201cParameterized Complexity: Exponential Speed-Up for Planar Graph Problems,\u201d in: Proceedings of ICALP 2001, Crete, Greece, Lecture Notes in Computer Science vol. 2076 (2001), 261\u2013272.","DOI":"10.1007\/3-540-48224-5_22"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","article-title":"\u201cFaster Exact Algorithms for Hard Problems: A Parameterized Point of View,\u201d","volume":"229","author":"Alber","year":"2001","journal-title":"Discrete Mathematics"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB4","doi-asserted-by":"crossref","unstructured":"S. Arora, \u201cPolynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems,\u201d In: Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996.","DOI":"10.1007\/3-540-63248-4_5"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB5","unstructured":"V. Arvind, \u201cOn the Parameterized Complexity of Counting Problems,\u201d Workshop on Parameterized Complexity, Madras, India, Dec. 2000."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB6","unstructured":"V. Arvind, M. R. Fellows, M. Mahajan, V. Raman, S. S. Rao, F. A. Rosamond, C. R. Subramanian, \u201cParametric Duality and Fixed Parameter Tractability\u201d, manuscript 2001."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB7","unstructured":"C. Bazgan, \u201cSch\u00e9mas d'approximation et complexit\u00e9 param\u00e9tr\u00e9e,\u201d Rapport de stage de DEA d'Informatique \u00e0 Orsay, 1995."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB8","first-page":"49","article-title":"\u201cParameterized Complexity Analysis in Computational Biology,\u201d","volume":"11","author":"Bodlaender","year":"1995","journal-title":"Computer Applications in the Biosciences"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB9","unstructured":"Leizhen Cai, \u201cThe Complexity of Coloring Parameterized Graphs,\u201d to appear in Discrete Applied Math."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB10","unstructured":"M. Cesati and M. Di Ianni, \u201cParameterized Parallel Complexity,\u201d Technical Report ECCC97-06, University of Trier, 1997."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB11","unstructured":"Liming Cai and D. Juedes, \u201cSubexponential Parameterized Algorithms Collapse the W-Hierarchy,\u201d in: Proceedings of ICALP 2001, Crete, Greece, LNCS 2076 (2001)."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB12","unstructured":"M. Cosner, R. Jansen, B. Moret, L. Raubeson, L. Wang, T. Warnow and S. Wyman, \u201cA New Fast Heuristic for Computing the Breakpoint Phylogeny and Experimental Phylogenetic Analyses of Real and Synthetic Data,\u201d manuscript, 2000."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB13","doi-asserted-by":"crossref","unstructured":"J. Chen, I.A. Kanj and W. Jia, \u201cVertex Cover: Further Observations and Further Improvements,\u201d Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science 1665 (1999), 313\u2013324.","DOI":"10.1007\/3-540-46784-X_30"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB14","unstructured":"P. Cheeseman, B. Kanefsky and W. Taylor, \u201cWhere the Really Hard Problems Are,\u201d Proc. 12th International Joint Conference on Artificial Intelligence (1991), 331\u2013337."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0166-218X(96)00074-1","article-title":"\u201cA Linear Time Algorithm for Computing the Intersection of All Odd Cycles in a Graph,\u201d","volume":"73","author":"Cai","year":"1997","journal-title":"Discrete Applied Math"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB16","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","article-title":"\u201cOn the Efficiency of Polynomial Time Approximation Schemes,\u201d","volume":"64","author":"Cesati","year":"1997","journal-title":"Information Processing Letters"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB17","doi-asserted-by":"crossref","unstructured":"M. Cesati and H. T. Wareham, \u201cParameterized Complexity Analysis in Robot Motion Planning,\u201d Proceedings 25th IEEE Intl. Conf. on Systems, Man and Cybernetics: Volume 1, IEEE Press, Los Alamitos, CA (1995), 880\u2013885.","DOI":"10.1109\/ICSMC.1995.537878"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB18","series-title":"Parameterized Complexity","author":"Downey","year":"1998"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB19","unstructured":"R. Downey and M. Fellows, \u201cParameterized Complexity After Almost Ten Years: Review and Open Questions,\u201d in: Combinatorics, Computation and Logic, DMTCS'99 and CATS'99, Australian Computer Science Communications, Springer-Verlag Singapore, vol. 21 (1999), 1\u201333."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB20","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows and U. Stege, \u201cParameterized Complexity: A Framework for Systematically Confronting Computational Intractability.\u201d In: Contemporary Trends in Discrete Mathematics, (R. Graham, J. Kratochvil, J. Nesetril and F. Roberts, eds.), Proceedings of the DIMACS-DIMATIA Workshop, Prague, 1997, AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49 (1999), 49\u201399.","DOI":"10.1090\/dimacs\/049\/04"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB21","unstructured":"R. G. Downey, M. Fellows and U. Taylor, \u201cThe Parameterized Complexity of Relational Database Queries and an Improved Characterization of W [1],\u201d in: Combinatorics, Complexity and Logic: Proceedings of DMTCS'96, Springer-Verlag (1997), 194\u2013213."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB22","unstructured":"F. Dehne, A. Rau-Chaplin, U. Stege and P. Taillon, \u201cSolving Large FPT Problems on Coarse Grained Parallel Machines,\u201d manuscript, 2001."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB23","doi-asserted-by":"crossref","unstructured":"H. Fernau, \u201cRemarks on Parameterized Enumeration,\u201d manuscript, 2001.","DOI":"10.1007\/3-540-45655-4_60"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB24","doi-asserted-by":"crossref","unstructured":"J. Flum and M. Grohe, \u201cDescribing Parameterized Complexity Classes,\u201d manuscript, 2001.","DOI":"10.1007\/3-540-45841-7_29"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB25","doi-asserted-by":"crossref","unstructured":"M. Fellows, C. McCartin, F. Rosamond and U. Stege, \u201cTrees with Few and Many Leaves,\u201d manuscript, full version of the paper: \u201cCoordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems,\u201d Proceedings of the 20th FST TCS Conference, New Delhi, India, Lecture Notes in Computer Science vol. 1974, Springer Verlag (2000), 240\u2013251.","DOI":"10.1007\/3-540-44450-5_19"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB26","series-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB27","unstructured":"G. Gutin and T. Kloks, \u201cKernels in Planar Digraphs,\u201d manuscript, 2001."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB28","doi-asserted-by":"crossref","unstructured":"M. Grohe, \u201cGeneralized Model-Checking Problems for First-Order Logic,\u201d Proc. STACS 2001, Springer-Verlag LNCS vol. 2001 (2001), 12\u201326.","DOI":"10.1007\/3-540-44693-1_2"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB29","doi-asserted-by":"crossref","unstructured":"M. Grohe, \u201cThe Parameterized Complexity of Database Queries,\u201d Proc. PODS 2001, ACM Press (2001), 82\u201392.","DOI":"10.1145\/375551.375564"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB30","doi-asserted-by":"crossref","unstructured":"G. Gottlob, F. Scarcello and M. Sideri, \u201cFixed Parameter Complexity in AI and Nonmonotonic Reasoning,\u201d to appear in The Artificial Intelligence Journal. Conference version in: Proc. of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99), vol. 1730 of Lecture Notes in Artificial Intelligence (1999), 1\u201318.","DOI":"10.1007\/3-540-46767-X_1"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB31","unstructured":"M. Hallett, G. Gonnett and U. Stege, \u201cVertex Cover Revisited: A Hybrid Algorithm of Theory and Heuristic,\u201d manuscript, 1998."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB32","doi-asserted-by":"crossref","unstructured":"F. Henglein and H. G. Mairson, \u201cThe Complexity of Type Inference for Higher-Order Typed Lambda Calculi.\u201d In Proc. Symp. on Principles of Programming Languages (POPL) (1991), 119\u2013130.","DOI":"10.1145\/99583.99602"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB33","doi-asserted-by":"crossref","unstructured":"S. Khanna and R. Motwani, \u201cTowards a Syntactic Characterization of PTAS,\u201d in: Proc. STOC 1996, ACM Press (1996), 329\u2013337.","DOI":"10.1145\/237814.237979"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB34","doi-asserted-by":"crossref","unstructured":"S. Khot and V. Raman, \u2018Parameterized Complexity of Finding Subgraphs with Hereditary properties\u2019, Proceedings of the Sixth Annual International Computing and Combinatorics Conference (COCOON 2000) July 2000, Sydney, Australia, Lecture Notes in Computer Science, Springer Verlag 1858 (2000) 137\u2013147.","DOI":"10.1007\/3-540-44968-X_14"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB35","doi-asserted-by":"crossref","unstructured":"O. Lichtenstein and A. Pneuli. \u201cChecking That Finite-State Concurrents Programs Satisfy Their Linear Specification.\u201d In: Proceedings of the 12th ACM Symposium on Principles of Programming Languages (1985), 97\u2013107.","DOI":"10.1145\/318593.318622"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB36","unstructured":"P. Moscato, \u201cControllability, Parameterized Complexity, and the Systematic Design of Evolutionary Algorithms,\u201d manuscript, 2001 (http:\/\/www.densis.fee.unicamp.br\/moscato)."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB37","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","article-title":"\u201cParameterizing Above Guaranteed Values: MaxSat and MaxCut,\u201d","volume":"31","author":"Mahajan","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB38","doi-asserted-by":"crossref","unstructured":"B. Moret, S. Wyman, D. Bader, T. Warnow and M. Yan, \u201cA New Implementation and Detailed Study of Breakpoint Analysis,\u201d manuscript, 2000.","DOI":"10.1142\/9789814447362_0056"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB39","doi-asserted-by":"crossref","unstructured":"R. Niedermeier, \u201cSome Prospects for Efficient Fixed-Parameter Algorithms,\u201d Proc. SOFSEM'98 Springer-Verlag LNCS 1521 (1998), 168\u2013185.","DOI":"10.1007\/3-540-49477-4_12"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB40","doi-asserted-by":"crossref","unstructured":"A. Natanzon, R. Shamir and R. Sharan, \u201cA Polynomial-Time Approximation Algorithm for Minimum Fill-In,\u201d Proc. ACM Symposium on the Theory of Computing (STOC'98), ACM Press (1998), 41\u201347.","DOI":"10.1145\/276698.276710"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB41","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis, \u201cOn the Complexity of Database Queries,\u201d Proc. ACM Symp. on Principles of Database Systems (1997), 12\u201319.","DOI":"10.1145\/263661.263664"},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB42","unstructured":"U. Stege, \u201cResolving Conflicts in Problems in Computational Biochemistry,\u201d Ph.D. dissertation, ETH, 2000."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB43","unstructured":"M. Truszczynski, \u201cOn Computing Large and Small Stable Models,\u201d to appear in Journal of Logic Programming."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB44","unstructured":"V. Raman, \u201cParameterized Complexity,\u201d in: Proceedings of the 7th National Seminar on Theoretical Computer Science, Chennai, India (1997), 1\u201318."},{"key":"10.1016\/S1571-0661(04)00301-9_NEWBIB45","article-title":"\u201cOn the Differences Between Practical and Applied,\u201d","author":"Weihe","year":"2000","journal-title":"Dagstuhl Workshop on Experimental Algorithmics"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104003019?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104003019?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:03:55Z","timestamp":1761609835000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066104003019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":45,"alternative-id":["S1571066104003019"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(04)00301-9","relation":{},"ISSN":["1571-0661"],"issn-type":[{"value":"1571-0661","type":"print"}],"subject":[],"published":{"date-parts":[[2002,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Parameterized Complexity","name":"articletitle","label":"Article Title"},{"value":"Electronic Notes in Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S1571-0661(04)00301-9","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2002 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}