{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T06:12:20Z","timestamp":1744697540838,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":53,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540003465"},{"type":"electronic","value":"9783540363835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36383-1_3","type":"book-chapter","created":{"date-parts":[[2007,6,3]],"date-time":"2007-06-03T20:26:41Z","timestamp":1180902401000},"page":"51-77","source":"Crossref","is-referenced-by-count":16,"title":["Parameterized Complexity: The Main Ideas and Connections to Practical Computing"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,12,16]]},"reference":[{"key":"3_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. Fixed parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73:235\u2013276, 1995.","journal-title":"Annals of Pure and Applied Logic"},{"key":"3_CR2","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of Scandinavian Workshop on Algorithms and Theory (SWAT\u201902)","author":"J. Alber","year":"2002","unstructured":"J. Alber, M. Fellows, and R. Niedermeier. Efficient data reduction for dominating set: a linear problem kernel for the planar case. To appear in the Proceedings of Scandinavian Workshop on Algorithms and Theory (SWAT\u201902). Springer Lecture Notes in Computer Science, 2002."},{"key":"3_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. Faster exact algorithms for hard problems: a parameterized point of view. Discrete Mathematics 229:3\u201327, 2001.","journal-title":"Discrete Mathematics"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS\u201996), pages 2\u201311, 1996.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 38th Annual IEEE Symposium on the Foundations of Computer Science (FOCS\u201997), pages 554\u2013563, 1997.","DOI":"10.1109\/SFCS.1997.646145"},{"key":"3_CR6","unstructured":"V. Arvind, M. R. Fellows, M. Mahajan, V. Raman, S. S. Rao, F. A. Rosamond, and C. R. Subramanian. Parametric duality and fixed parameter tractability. Manuscript, 2001."},{"key":"3_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation. Springer-Verlag, Heidelberg, 1999."},{"key":"3_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-46632-0_26","volume-title":"Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC\u201999)","author":"N. Bansal","year":"1999","unstructured":"N. Bansal and V. Raman. Upper bounds for MaxSat: further improved. In Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC\u201999). Springer Lecture Notes in Computer Science 1741, pages 247\u2013258, 1999."},{"key":"3_CR9","unstructured":"C. Bazgan. Sch\u00e9mas d\u2019approximation et complexit\u00e9 param\u00e9tr\u00e9e. Rapport de stage de DEA d\u2019Informatique \u00e0 Orsay, 1995."},{"key":"3_CR10","first-page":"25","volume-title":"Genome Informatics 1997","author":"M. Blanchette","year":"1997","unstructured":"M. Blanchette, G. Bourque, and D. Sankoff. Breakpoint phylogenies. In S. Miyano and T. Tagaki, editors, Genome Informatics 1997, Universal Academy Press, Tokyo, 1997, pages 25\u201334."},{"key":"3_CR11","unstructured":"L. Cai. The complexity of coloring parameterized graphs. To appear in Discrete Applied Mathematics."},{"key":"3_CR12","unstructured":"L. Cai, M. Fellows, D. Juedes, and F. Rosamond. Efficient polynomial-time approximation schemes for problems on planar structures: upper and lower bounds. Manuscript, 2001."},{"key":"3_CR13","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. On the efficiency of polynomial time approximation schemes. Information Processing Letters 64:165\u2013171, 1997.","journal-title":"Information Processing Letters"},{"key":"3_CR14","first-page":"880","volume":"1","author":"M. Cesati","year":"1995","unstructured":"M. Cesati and H. T. Wareham. Parameterized complexity analysis in robot motion planning. In Proceedings of the 25th IEEE International Conference on Systems, Man and Cybernetics: Volume 1. IEEE Press, Los Alamitos, CA, pages 880\u2013885, 1995.","journal-title":"Proceedings of the 25th IEEE International Conference on Systems, Man and Cybernetics"},{"key":"3_CR15","unstructured":"P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pages 331\u2013337, 1991."},{"key":"3_CR16","unstructured":"C. Chekuri and S. Khanna. A PTAS for the multiple knapsack problem. Manuscript, 2000."},{"key":"3_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201999)","author":"J. Chen","year":"1999","unstructured":"J. Chen, I. A. Kanj, and W. Jia. Vertex cover: further observations and further improvements. In Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201999). Springer Lecture Notes in Computer Science 1665, pages 313\u2013324, 1999."},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"J. Chen and A. Miranda. A polynomial-time approximation scheme for general multiprocessor scheduling. In Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (STOC\u201999), pages 418\u2013427, 1999.","DOI":"10.1145\/301250.301363"},{"key":"3_CR19","unstructured":"F. Dehne, A. Rau-Chaplin, U. Stege, and P. Taillon. Solving large FPT problems on coarse grained parallel machines. Manuscript, 2001."},{"key":"3_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-45678-3_3","volume-title":"Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC\u201901)","author":"X. Deng","year":"2001","unstructured":"X. Deng, H. Feng, P. Zhang, and H. Zhu. A polynomial time approximation scheme for minimizing total completion time of unbounded batch scheduling. In Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC\u201901). Springer Lecture Notes in Computer Science 2223, pages 26\u201335, 2001."},{"key":"3_CR21","volume-title":"Parameterized Complexity","author":"R. G. Downey","year":"1998","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, Heidelberg, 1998."},{"key":"3_CR22","first-page":"1","volume":"21","author":"R. G. Downey","year":"1999","unstructured":"R. G. Downey and M. Fellows. Parameterized complexity after almost ten years: review and open questions. In Proceedings of Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999, Australian Computer Science Communications, Springer-Verlag, Singapore, vol. 21, pages 1\u201333, 1999.","journal-title":"Proceedings of Combinatorics, Computation and Logic, DMTCS\u201999 and CATS\u201999"},{"key":"3_CR23","unstructured":"R. G. Downey, M. Fellows, and U. Taylor. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Combinatorics, Complexity and Logic: Proceedings of DMTCS\u201996. Springer-Verlag, Heidelberg, pages 194\u2013213, 1997."},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows, and U. Stege. Parameterized complexity: a framework for systematically confronting computational intractability. In R. Graham, J. Kratochv\u00edl, J. Nesetril, and F. Roberts, editors, Proceedings of the DIMACS-DIMATIA Workshop, Prague, 1997. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, pages 49\u201399, 1999.","DOI":"10.1090\/dimacs\/049\/04"},{"key":"3_CR25","unstructured":"T. Erlebach, K. Jansen, and E. Seidel. Polynomial time approximation schemes for geometric graphs. In Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA\u201901), pages 671\u2013679, 2001."},{"key":"3_CR26","series-title":"Lect Notes Comput Sci","first-page":"240","volume-title":"Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems","author":"M. Fellows","year":"2000","unstructured":"M. Fellows, C. McCartin, F. Rosamond, and U. Stege. Trees with few and many leaves. Manuscript, full version of the paper: Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings of the 20th FSTTCS Conference. Springer Lecture Notes in Computer Science 1974, pages 240\u2013251, 2000."},{"key":"3_CR27","unstructured":"J. Felsenstein. Private communication, 1997."},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"M. Galota, C. Glasser, S. Reith, and H. Vollmer. A polynomial time approximation scheme for base station positioning in UMTS networks. In Proceedings of Discrete Algorithms and Methods for Mobile Computing and Communication, 2001.","DOI":"10.1145\/381448.381455"},{"key":"3_CR29","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979."},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"G. Gottlob, F. Scarcello, and M. Sideri. Fixed parameter complexity in AI and nonmonotonic reasoning. To appear in The Artificial Intelligence Journal. Conference version in Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201999), Springer Lecture Notes in Artificial Intelligence 1730, pages 1\u201318, 1999.","DOI":"10.1007\/3-540-46767-X_1"},{"key":"3_CR31","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/3-540-46521-9_15","volume-title":"Proceedings of the 4th Italian Conference on Algorithms and Complexity","author":"J. Gramm","year":"2000","unstructured":"J. Gramm and R. Niedermeier. Faster exact algorithms for Max2Sat. In Proceedings of the 4th Italian Conference on Algorithms and Complexity. Springer Lecture Notes in Computer Science 1767, pages 174\u2013186, 2000."},{"key":"3_CR32","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/3-540-44693-1_2","volume-title":"Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901)","author":"M. Grohe","year":"2001","unstructured":"M. Grohe. Generalized model-checking problems for first-order logic. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201901). Springer Lecture Notes in Computer Science 2010, pages 12\u201326, 2001."},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"M. Grohe. The parameterized complexity of database queries. In Proceedings of the 20th ACM symposium on Principles of Database Systems (PODS\u201901), ACM Press, pages 82\u201392, 2001.","DOI":"10.1145\/375551.375564"},{"key":"3_CR34","unstructured":"M. Hallett, G. Gonnett, and U. Stege. Vertex cover revisited: a hybrid algorithm of theory and heuristic. Manuscript, 1998."},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"F. Henglein and H. G. Mairson. The complexity of type inference for higher-order typed lambda calculi. In Proceedings of the 18th Annual ACM Symposium on Principles of Programming Languages (POPL\u201991), pages 119\u2013130, 1991.","DOI":"10.1145\/99583.99602"},{"key":"3_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/3-540-45678-3_4","volume-title":"Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC\u201901)","author":"Y. Karuno","year":"2001","unstructured":"Y. Karuno and H. Nagamochi. A polynomial time approximation scheme for the multi-vehicle scheduling problem on a path with release and handling times. In Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC\u201901). Springer Lecture Notes in Computer Science 2223, 36\u201347, 2001."},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"S. Khanna and R. Motwani. Towards a syntactic characterization of PTAS. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC\u201996), pages 329\u2013337, 1996.","DOI":"10.1145\/237814.237979"},{"key":"3_CR38","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/3-540-44968-X_14","volume-title":"Proceedings of the 6th Annual International Computing and Combinatorics Conference (COCOON\u201900)","author":"S. Khot","year":"2000","unstructured":"S. Khot and V. Raman. Parameterized complexity of finding subgraphs with hereditary properties. In Proceedings of the 6th Annual International Computing and Combinatorics Conference (COCOON\u201900). Springer Lecture Notes in Computer Science 1858, pages 137\u2013147, 2000."},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"O. Lichtenstein and A. Pneuli. Checking that Finite-state concurrents programs satisfy their linear specification. In Proceedings of the 12th ACM Symposium on Principles of Programming Languages (POPL\u201985), pages 97\u2013107, 1985.","DOI":"10.1145\/318593.318622"},{"key":"3_CR40","doi-asserted-by":"crossref","unstructured":"B. Moret, S. Wyman, D. Bader, T. Warnow, and M. Yan. A new implementation and detailed study of breakpoint analysis. In Proceedings of the 6th Pacific Symposium on Biocomputing (PSB\u201901), pages 583\u2013594, 2001.","DOI":"10.1142\/9789814447362_0056"},{"key":"3_CR41","unstructured":"P. Moscato. Controllability, parameterized complexity, and the systematic design of evolutionary algorithms. Manuscript, 2001. See http:\/\/www.densis.fee.unicamp.br\/~moscato"},{"key":"3_CR42","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-49477-4_12","volume-title":"Proceedings of the 25th Conference on Current Trends in Theory and Practice oof Informatics (SOFSEM\u201998)","author":"R. Niedermeier","year":"1998","unstructured":"R. Niedermeier. Some prospects for efficient fixed-parameter algorithms. In Proceedings of the 25th Conference on Current Trends in Theory and Practice oof Informatics (SOFSEM\u201998). Springer Lecture Notes in Computer Science 1521, pages 168\u2013185, 1998."},{"key":"3_CR43","doi-asserted-by":"crossref","unstructured":"R. Niedermeier and P. Rossmanith. An efficient fixed parameter algorithm for 3-hitting set. Journal of Discrete Algorithms 2(1), 2001.","DOI":"10.1016\/S1570-8667(03)00009-1"},{"key":"3_CR44","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. On the complexity of database queries. In Proceedings of the 16th ACM Symposium on Principles of Database Systems (PODS\u201997), pages 12\u201319, 1997.","DOI":"10.1145\/263661.263664"},{"key":"3_CR45","unstructured":"I. Pe'er and R. Shamir. The median problems for breakpoints are NP-complete. Electronic Colloquium on Computational Complexity Technical Report 98-071, http:\/\/www.ecc.uni-trier.de\/eccc ."},{"key":"3_CR46","unstructured":"V. Raman. Parameterized complexity. In Proceedings of the 7th National Seminar on Theoretical Computer Science, Chennai, India, pages 1\u201318, 1997."},{"key":"3_CR47","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/3-540-44436-X_24","volume-title":"Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u2019 00)","author":"H. Shachnai","year":"2000","unstructured":"H. Shachnai and T. Tamir. Polynomial time approximation schemes for class-constrained packing problems. In Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u2019 00). Springer Lecture Notes in Computer Science 1913, pages 144\u2013154, 2000."},{"key":"3_CR48","unstructured":"R. Shamir and D. Tzur. The maximum subforest problem: approximation and exact algorithms. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998), pages 394\u2013399, 1998."},{"key":"3_CR49","unstructured":"U. Stege. Resolving conflicts in problems in computational biochemistry. Ph.D. dissertation, ETH, 2000."},{"key":"3_CR50","unstructured":"M. Truszczynski. On Computing Large and Small Stable Models. In Proceedings of the International Conference on Logic Programming, pages 169\u2013183, 1999. Full version to appear in Journal of Logic Programming."},{"key":"3_CR51","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proceedings of the 1st Workshop on Algorithm Engineering and Experiments (ALENEX\u201998)","author":"K. Weihe","year":"1998","unstructured":"K. Weihe. Covering trains by stations, or the power of data reduction. In Proceedings of the 1st Workshop on Algorithm Engineering and Experiments (ALENEX\u201998). Springer Lecture Notes in Computer Science 1619, pages 1\u20138, 1998."},{"key":"3_CR52","doi-asserted-by":"crossref","unstructured":"K. Weihe. On the differences between practical and applied. Dagstuhl Workshop on Experimental Algorithmics, September 2000.","DOI":"10.1007\/3-540-44691-5_1"},{"key":"3_CR53","unstructured":"B. Wu, G. Lancia, V. Bafna, K-M. Chao, R. Ravi, and C. Tang. A polynomial time approximation scheme for minimum routing cost spanning trees. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998), pages 21\u201332, 1998."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36383-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T22:04:24Z","timestamp":1737065064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36383-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540003465","9783540363835"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/3-540-36383-1_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}