{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:27Z","timestamp":1725558387288},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405450"},{"type":"electronic","value":"9783540450788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45078-8_44","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T17:23:52Z","timestamp":1277227432000},"page":"505-519","source":"Crossref","is-referenced-by-count":14,"title":["New Directions and New Challenges in Algorithm Design and Complexity, Parameterized"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"44_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (1999)"},{"key":"44_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/3-540-45471-3_16","volume-title":"Algorithm Theory - SWAT 2002","author":"J. Alber","year":"2002","unstructured":"Alber, J., Fellows, M., Niedermeier, R.: Efficient Data Reduction for Dominating Set: A Linear Problem Kernel for the Planar Case. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 150\u2013159. Springer, Heidelberg (2002)"},{"key":"44_CR3","unstructured":"Abu-Khzam, F., Fellows, M., Langston, M., Rosamond, F.: Bounded Vertex Cover Structure and the Design of FPT Algorithms (2003) (manuscript)"},{"key":"44_CR4","unstructured":"Abu-Khzam, F., Langston, M.A., Shanbhag, P., Symons, C.T.: High Performance Tools for Fixed-Parameter Tractable Implementations. In: WADS 2003 Workshop Presentation (2003)"},{"key":"44_CR5","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Prof verification and intractability of optimization problems. In: Proceedings of the IEEE Symposium on the Foundations of Computer Science (1992)"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Arora, S.: Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. In: Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pp. 2\u201312 (1996)","DOI":"10.1109\/SFCS.1996.548458"},{"key":"44_CR7","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1109\/SFCS.1997.646145","volume-title":"Proc. 38th Annual IEEE Symposium on the Foundations of Computing (FOCS 1997)","author":"S. Arora","year":"1997","unstructured":"Arora, S.: Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. In: Proc. 38th Annual IEEE Symposium on the Foundations of Computing (FOCS 1997), pp. 554\u2013563. IEEE Press, Los Alamitos (1997)"},{"key":"44_CR8","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM\u00a042, 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"key":"44_CR9","unstructured":"Bazgan, C.: Sch\u00e9mas d\u2019approximation et complexit\u00e9 param\u00e9tr\u00e9e. Rapport de stage de DEA d\u2019Informatique \u00e0 Orsay (1995)"},{"key":"44_CR10","doi-asserted-by":"crossref","unstructured":"Bonsma, P.S., Br\u00fcggemann T., Woeginger, G.J.: A faster FPT algorithm for finding spanning trees with many leaves (2003) (manuscript)","DOI":"10.1007\/978-3-540-45138-9_20"},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On Linear Time Minor Tests and Depth-First Search. Journal of Algorithms\u00a014, 1\u201323 (1993)","journal-title":"Journal of Algorithms"},{"key":"44_CR12","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R., Fellows, M.: On the Parameterized Complexity of Short Computation and Factorization. Archive for Mathematical Logic\u00a036, 321\u2013337 (1997)","journal-title":"Archive for Mathematical Logic"},{"key":"44_CR14","unstructured":"Cai, L., Fellows, M., Juedes, D., Rosamond, F.: Efficient Polynomial-Time Approximation Schemes for Problems on Planar Structures: Upper and Lower Bounds (2001) (manuscript)"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Cai, L., Juedes, D.: On the Existence of Subexponential Parameterized Algorithms (2001) (manuscript); Revised version of the paper, Subexponential Parameterized Algorithms Collapse the W-Hierarchy. In: Proceedings 28th ICALP, Springer-Verlag LNCS 2076, pp. 273\u2013284 (2001); (The conference version contains some major flaws)","DOI":"10.1007\/3-540-48224-5_23"},{"key":"44_CR16","unstructured":"Chekuri, C., Khanna, S.: A PTAS for the Multiple Knapsack Problem. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 213\u2013222 (2000)"},{"key":"44_CR17","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further Observations and Further Improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"44_CR18","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1145\/301250.301363","volume-title":"Proc. ACM Symposium on Theory of Computing (STOC 1999)","author":"J. Chen","year":"1999","unstructured":"Chen, J., Miranda, A.: A Polynomial-Time Approximation Scheme for General Multiprocessor Scheduling. In: Proc. ACM Symposium on Theory of Computing (STOC 1999), pp. 418\u2013427. ACM Press, New York (1999)"},{"key":"44_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Trevisan, L.: On the Efficiency of Polynomial Time Approximation Schemes. Information Processing Letters\u00a064, 165\u2013171 (1997)","journal-title":"Information Processing Letters"},{"key":"44_CR20","doi-asserted-by":"crossref","unstructured":"Downey, R., Estivill-Castro, V., Fellows, M., Prieto-Rodriguez, E., Rosamond, F.: Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems. Electronic Notes in Theoretical Computer Science 78, 205\u2013218 (2003)","DOI":"10.1016\/S1571-0661(04)81014-4"},{"key":"44_CR21","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Computational Feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkhauser, Boston (1995)"},{"key":"44_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed Parameter Tractability and Completeness II: Completeness for W[1]. Theoretical Computer Science A\u00a0141, 109\u2013131 (1995)","journal-title":"Theoretical Computer Science A"},{"key":"44_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"44_CR24","unstructured":"Downey, R., Fellows, M., Prieto-Rodriguez, E., Rosamond, F.: Fixedparameter Tractability and Completeness V: Parametric Miniatures (2003) (manuscript)"},{"key":"44_CR25","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Stege, U.: Parameterized Complexity: A Framework for Systematically Confronting Computational Intractability. In: Graham, R., Kratochv\u00edl, J., Nestr\u00edl, J., Roberts, F. (eds.) Proceedings of the DIMACS DIMATIA Workshop, Prague, 1997. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a049, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"44_CR26","volume-title":"Proceedings of the IEEE Computational Complexity Conference (CCC 2003)","author":"R. Downey","year":"2003","unstructured":"Downey, R.: Parameterized Complexity for the Skeptic. In: Proceedings of the IEEE Computational Complexity Conference (CCC 2003). IEEE Press, Los Alamitos (2003) (to appear)"},{"key":"44_CR27","unstructured":"Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.: Solving Large FPT Problems on Coarse Grained Parallel Machines (2002) (manuscript)"},{"key":"44_CR28","first-page":"368","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 1991)","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree Automata, \u03bc-Calculus and Determinacy. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 1991), pp. 368\u2013377. IEEE Press, Los Alamitos (1991)"},{"key":"44_CR29","first-page":"671","volume-title":"Proc. ACM Symposium on Discrete Algorithms (SODA 2001)","author":"T. Erlebach","year":"2001","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial Time Approximation Schemes for Geometric Graphs. In: Proc. ACM Symposium on Discrete Algorithms (SODA 2001), pp. 671\u2013679. ACM Press, New York (2001)"},{"key":"44_CR30","unstructured":"Fellows, M., Gramm, J., Niedermeier, R.: On the Parameterized Intractability of Motif Search Problems (2003) (manuscript)"},{"key":"44_CR31","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: On Well-Partial-Order Theory and its Applications to Combinatorial Problems of VLSI Design. SIAM Journal on Discrete Mathematics\u00a05, 117\u2013126","DOI":"10.1137\/0405010"},{"key":"44_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/3-540-44450-5_19","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"M. Fellows","year":"2000","unstructured":"Fellows, M., McCartin, C., Rosamond, F., Stege, U.: Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol.\u00a01974, pp. 240\u2013251. Springer, Heidelberg (2000)"},{"key":"44_CR33","doi-asserted-by":"crossref","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A Polynomial Algorithm for the k-Cut Problem. In: Proc. 29th Annual Symp. on the Foundations of Computer Science (FOCS), pp. 444-451 (1988)","DOI":"10.1109\/SFCS.1988.21960"},{"key":"44_CR34","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O. Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A Polynomial Algorithm for the k-Cut Problem for Fixed k. Mathematics of Operations Research\u00a019, 24\u201337 (1994)","journal-title":"Mathematics of Operations Research"},{"key":"44_CR35","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions and Tratable Queries. In: Proceedings of the 18th ACM Symposium on Database Systems, pp. 21\u201332 (1999)","DOI":"10.1145\/303976.303979"},{"key":"44_CR36","unstructured":"Grohe, M.: The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side (2003) (manuscript)"},{"key":"44_CR37","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Scarcello, F., Sideri, M.: Fixed Parameter Complexity in AI and Nonmonotonic Reasoning. To appear in The Artificial Intelligence Journal. Conference version in: Proc. of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 1999), vol. 1730 of Lecture Notes in Artificial Intelligence pp. 1\u201318 (1999)","DOI":"10.1007\/3-540-46767-X_1"},{"key":"44_CR38","unstructured":"Hallett, M.: Presentation at the Annual Conference of the New Zealand Mathematics Research Institute, New Plymouth (January 2003)"},{"key":"44_CR39","first-page":"329","volume-title":"Proc. STOC 1996","author":"S. Khanna","year":"1996","unstructured":"Khanna, S., Motwani, R.: Towards a Syntactic Characterization of PTAS. In: Proc. STOC 1996, pp. 329\u2013337. ACM Press, New York (1996)"},{"key":"44_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/3-540-44968-X_14","volume-title":"Computing and Combinatorics","author":"S. Khot","year":"2000","unstructured":"Khot, S., Raman, V.: Parameterized Complexity of Finding Subgraphs with Hereditary properties. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol.\u00a01858, pp. 137\u2013147. Springer, Heidelberg (2000)"},{"key":"44_CR41","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A New Approach to the Minimum Cut Problem. Journal of the ACM\u00a043, 601\u2013640 (1996)","journal-title":"Journal of the ACM"},{"key":"44_CR42","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H.W. Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research\u00a08, 538\u2013548 (1983)","journal-title":"Mathematics of Operations Research"},{"key":"44_CR43","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E. Luks","year":"1982","unstructured":"Luks, E.: Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. Journal of Computing and Systems Sciences\u00a025, 42\u201365 (1982)","journal-title":"Journal of Computing and Systems Sciences"},{"key":"44_CR44","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing Above Guaranteed Values: MaxSat and MaxCut. J. Algorithms\u00a031, 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"44_CR45","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Habilitationschrift, University of T\u00fcbingen (2002)"},{"key":"44_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"STACS 99","author":"R. Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: Upper Bounds for Vertex Cover Further Improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 561\u2013570. Springer, Heidelberg (1999)"},{"key":"44_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-540-45078-8_41","volume-title":"Algorithms and Data Structures","author":"E. Prieto","year":"2003","unstructured":"Prieto, E., Sloper, C.: Either\/Or: Using Vertex Cover Structure in Designing FPT Algorithms \u2014 the Case of k-Internal Spanning Tree. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 474\u2013483. Springer, Heidelberg (2003)"},{"key":"44_CR48","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"44_CR49","first-page":"394","volume-title":"Proc. ACM Symposium on Discrete Algorithms (SODA 1998)","author":"R. Shamir","year":"1998","unstructured":"Shamir, R., Tzur, D.: The Maximum Subforest Problem: Approximation and Exact Algorithms. In: Proc. ACM Symposium on Discrete Algorithms (SODA 1998), pp. 394\u2013399. ACM Press, New York (1998)"},{"key":"44_CR50","unstructured":"Weihe, K.: Covering Trains by Stations, or the Power of Data Reduction. In: Proc. ALEX 1998, pp. 1\u20138 (1998)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45078-8_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T05:48:40Z","timestamp":1559195320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45078-8_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405450","9783540450788"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45078-8_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}