{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T12:09:59Z","timestamp":1743077399199,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540429852"},{"type":"electronic","value":"9783540456780"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45678-3_26","type":"book-chapter","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T16:12:14Z","timestamp":1195143134000},"page":"291-307","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Parameterized Complexity: The Main Ideas and Some Research Frontiers"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,12,4]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K. Abrahamson","year":"1995","unstructured":"K. Abrahamson, R. Downey and M. Fellows, \u201cFixed Parameter Tractability and Completeness IV:O Completeness for WPad PSPACE Analogs,\u201dAnnals of Pure and Applied Logic 73 (1995),235\u2013276.","journal-title":"Annals of Pure and Applied Logic"},{"key":"26_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-48224-5_22","volume-title":"Parameterized Complexity:Exponential Speed-Up for Planar Graph Problems","author":"J. Alber","year":"2001","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."},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","volume":"229","author":"J. Alber","year":"2001","unstructured":"J. Alber, J. Gramm and R. Niedermeier, \u201cFaster Exact Algorithms for Hard Prob-lems:AParameterized Point of View,rd Discrete Mathematics 229 (2001),3\u201327.","journal-title":"Discrete Mathematics"},{"key":"26_CR4","unstructured":"S. Arora, \u201cPolynomial Time Approximatio Schemes for Euclidea TSP and Other Geometric Problems,\u201d in:Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996."},{"key":"26_CR5","unstructured":"V. Arvind, \u201cOn the Parameterized Complexity of Counting Problems,\u201dWorkshop on Parameterized Complexity... Madras,India,Dec.2000."},{"key":"26_CR6","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":"26_CR7","unstructured":"C. Bazgan, \u201cSch\u00e9mas d\u2019approximation et complexit\u00e9 param\u00e9tr\u00e9e,\u201d apport de stage de DEA d\u2019Informatique \u00e0 Orsay,1995."},{"key":"26_CR8","first-page":"49","volume":"11","author":"H. Bodlaender","year":"1995","unstructured":"H. Bodlaender, R. Downey, M. Fellows, M. Hallett and H.T. Wareham, \u201cParameterized Complexity Analysis in Computational Biology,\u201dComputer Applications in the Biosciences 11 (1995),49\u201357.","journal-title":"Computer Applications in the Biosciences"},{"key":"26_CR9","unstructured":"Leizhe Cai,?\u201cThe Complexity of Coloring Parameterized Graphs,\u201d to appear in Discrete Applied Math."},{"key":"26_CR10","unstructured":"M. Cesati and M. Di Ianni, \u201cParameterized Parallel Complexity,\u201d Technical Report ECCC97-06,University of Trier,1997."},{"key":"26_CR11","series-title":"Lect Notes Comput Sci","volume-title":"Subexpone tial Parameterized Algorithms Collapse the W Hierarchy","author":"L. Cai","year":"2001","unstructured":"Liming Cai and D. Juedes, \u201cSubexpone tial Parameterized Algorithms Collapse the W Hierarchy,\u201d in:Proceedings of ICALP 2001,Crete,Greece,LNCS 2076 (2001).304"},{"key":"26_CR12","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":"26_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"\u201cVertex Cover:Further Observations and Fur-ther Improvements","author":"J. Chen","year":"1999","unstructured":"J. Chen, I.A. Kanj and W. Jia, \u201cVertex Cover:Further Observations and Fur-ther Improvements,\u201dProceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u20199),Lecture Notes in Computer Science 1665 (1999),313\u2013324."},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0166-218X(96)00074-1","volume":"73","author":"L. Cai","year":"1997","unstructured":"Leizhe Cai and B. Schieber,\u201cA Linear Time Algorithm for Computing the Inter-section of All Odd Cycles i a Graph,\u201dDiscrete Applied Math. 73 (1997),27\u201334.","journal-title":"Discrete Applied Math."},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"M. Cesati and L. Trevisan, \u201cOn the Efficiency of Polynomial Time Approximation Schemes,\u201dInformation Processing Letters 64 (1997),165\u2013171.","journal-title":"Information Processing Letters"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"M. Cesati and H.T. Wareham, \u201cParameterized Complexity Analysis in Robot Motio Planning,\u201dProceedings 25th IEEE Intl. Conf. on Systems, Man and Cy-bernetics: Volume 1, IEEE Press, Los Alamitos,CA (1995),880\u2013885.","DOI":"10.1109\/ICSMC.1995.537878"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"R.G. Downey and M.R. Fellows,Parameterized Complexity, Springer-Verlag, 1998.291,295,297","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"26_CR18","first-page":"1","volume":"21","author":"R. Downey","year":"1999","unstructured":"R. Downey and M. Fellows, \u201cParameterized Complexity After Almost Ten Years:Review and Open Questions,\u201d in:Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999... Australia Computer Science Communicatio s, Springer-Verlag Singapore,vol.21 (1999),1\u201333.","journal-title":"Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows and U. Stege, \u201cParameterized Complexity:AFrame-work for Systematically Confronting Computational Intractability.\u201d in:Contempo-rary Trends in Discrete Mathematics, (R. Graham, J. Kratochv\u00edl, 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":"26_CR20","unstructured":"R.G. Downey, M. Fellows and U. Taylor, \u201cThe Parameterized Complexity of Rela-tional Database Queries a d an Improved Characterization of W[1],\u201d in:Combina-torics, Complexity and Logic: Proceedings of DMTCS\u201996... Springer-Verlag (1997), 194\u2013213."},{"key":"26_CR21","unstructured":"F. Deh e, A. Rau-Chaplin, U. Stege and P. Taillon, \u201cSolving Large FPT Problems on Coarse Grained Parallel Machines, manuscript,2001."},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"H. Fernau, \u201cRemarks of Parameterized Enumeration,\u201d manuscript,2001.","DOI":"10.1007\/3-540-45655-4_60"},{"key":"26_CR23","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":"26_CR24","series-title":"Lect Notes Comput Sci","first-page":"240","volume-title":"Trees with Few and Many Leaves","author":"M. Fellows","year":"2000","unstructured":"M. Fellows, C. McCarti, 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,\u201dProceedings of the 20th FST TCS Conference... New Delhi,India,Lecture Notes in Computer Science vol.1974,Springer Verlag (2000),240\u2013251."},{"key":"26_CR25","unstructured":"M. Garey and D. Johnso.Computers and Intractability: A Guide to the Theory of NP-completeness W.H. Freeman,San Francisco,1979."},{"key":"26_CR26","unstructured":"G. Guti and T. Kloks, \u201cKernels in Planar Digraphs,\u201d?manuscript,2001."},{"key":"26_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/3-540-44693-1_2","volume-title":"Generalized Model-Checking Problems for First-Order Logic","author":"M. Grohe","year":"2001","unstructured":"M. Grohe, \u201cGeneralized Model-Checking Problems for First-Order Logic,\u201dProc. STACS 2001... Springer-Verlag LNCS vol.2001 (2001),12\u201326."},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"M. Grohe, \u201cThe Parameterized Complexity of Database Queries,\u201dProc. PODS 2001... ACM Press (2001),82\u201392.","DOI":"10.1145\/375551.375564"},{"key":"26_CR29","unstructured":"G. Gottlob, F. Scarcello and M. Sideri, \u201cFixed Parameter Complexity in AI and No monotonic Reasoning,\u201d?to appear in The Artificial Intelligence Journal Co-fere ce version in:Proc. of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR ?9),vol.1730 of Lecture Notes in Artificial Intelligence (1999),1\u201318."},{"key":"26_CR30","unstructured":"M. Hallett, G. Gonnett and U. Stege, \u201cVertex Cover Revisited:AHybrid Algorithm of Theory and Heuristic,\u201d?manuscript,1998."},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"F. Hanglein and H. G. Mairson,\u201cThe Complexity of Type Inference for Higher-Order Typed Lambda Calculi.\u201dI Proc. Symp. on Principles of Programming Languages (POPL) (1991),119\u2013130.","DOI":"10.1145\/99583.99602"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"S. Khanna and R. Motwani,\u201cTowards a Syntactic Characterizatio of PTAS,\u201d in: Proc. STOC 1996... ACM Press (1996),329\u2013337.","DOI":"10.1145\/237814.237979"},{"key":"26_CR33","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/3-540-44968-X_14","volume-title":"Parameterized Complexity of Finding Subgraphs with Hereditary properties","author":"S. Khot","year":"2000","unstructured":"S. Khot and V. Rama,\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."},{"key":"26_CR34","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":"26_CR35","unstructured":"P. Moscato,\u201cControllability,Parameterized Complexity,and the Systematic Design of Evolutionary Algorithms,\u201d manuscript, 2001 ( http:\/\/www.densis.fee.unicamp.br\/~moscato )."},{"key":"26_CR36","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"M. Mahajan and V. Rama,\u201cParameterizing Above Guaranteed Values:MaxSat and MaxCut,\u201d J. Algorithms 31 (1999), 335\u2013354.","journal-title":"J. Algorithms"},{"key":"26_CR37","doi-asserted-by":"crossref","unstructured":"B. Moret, S. Wyma, 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":"26_CR38","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-49477-4_12","volume-title":"Some Prospects for Efficient Fixed-Parameter Algorithms","author":"R. Niedermier","year":"1998","unstructured":"R. Niedermeier,\u201cSome Prospects for Efficient Fixed-Parameter Algorithms,\u201d Proc. SOFSEM\u201998 Springer-Verlag LNCS 1521 (1998), 168\u2013185."},{"key":"26_CR39","doi-asserted-by":"crossref","unstructured":"A. Natanzon, R. Shamir and R. Sharan,\u201cA Polynomial-Time Approximatio Algorithm for Minimum Fill-I,\u201d Proc. ACM Symposium on the Theory of Computing (STOC\u201998),ACM Press (1998),41\u201347.","DOI":"10.1145\/276698.276710"},{"key":"26_CR40","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":"26_CR41","unstructured":"U. Stege,\u201cResolving Conflicts in Problems in Computational Biochemistry,\u201d Ph.D. dissertation, ETH, 2000."},{"key":"26_CR42","unstructured":"M. Truszczynski,\u201cOn Computing Large and Small Stable Models,\u201d to appear in Journal of Logic Programming."},{"key":"26_CR43","unstructured":"V. Rama, \u201cParameterized Complexity,\u201d in:Proceedings of the 7th National Semstm on Theoretical Computer Science, Chennai, India (1997), 1\u201318."},{"key":"26_CR44","doi-asserted-by":"crossref","unstructured":"K. Weihe, \u201cOn the Differences Betwee Practical and Applied,\u201d Dagstuhl Workshop on Experime tal Algorithmics, September 2000.","DOI":"10.1007\/3-540-44691-5_1"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45678-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T11:35:17Z","timestamp":1737545717000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45678-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540429852","9783540456780"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/3-540-45678-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"4 December 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}