{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:46:54Z","timestamp":1760028414959},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_1","type":"book-chapter","created":{"date-parts":[[2010,9,4]],"date-time":"2010-09-04T01:16:57Z","timestamp":1283563017000},"page":"1-12","source":"Crossref","is-referenced-by-count":37,"title":["Blow-Ups, Win\/Win\u2019s, and Crown Rules: Some New Directions in FPT"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","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":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-44683-4_11","volume-title":"Mathematical Foundations of Computer Science 2001","author":"J. Alber","year":"2001","unstructured":"Alber, J., Fan, H., Fellows, M., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: Refined Search Tree Techniques for the Planar Dominating Set Problem. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 111\u2013122. Springer, Heidelberg (2001)"},{"key":"1_CR3","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":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved Tree Decomposition Based Algorithms for Domination-Like Problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 613\u2013627. Springer, Heidelberg (2002)"},{"key":"1_CR5","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 (1996), pp. 2\u201312 (1996)","DOI":"10.1109\/SFCS.1996.548458"},{"key":"1_CR6","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":"1_CR7","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":"1_CR8","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":"1_CR9","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":"1_CR10","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":"1_CR11","unstructured":"Chor, B., Fellows, M., Juedes, D.: An Efficient FPT Algorithm for Saving k Colors (2003) (manuscript)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Cai, L., Juedes, D.: On the Existence of Subexponential Parameterized Algorithms. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 273\u2013284. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-48224-5_23"},{"key":"1_CR13","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":"1_CR14","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":"1_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"R. Downey","year":"2003","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\u00a078, 205\u2013218 (2003)","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Computational Feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, Birkhauser, Boston, pp. 219\u2013244 (1995)","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"1_CR17","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":"1_CR18","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":"1_CR19","unstructured":"Downey, R., Fellows, M., Prieto-Rodriguez, E., Rosamond, F.: Fixed-parameter Tractability and Completeness V: Parametric Miniatures (2003) (manuscript)"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-540-39890-5_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Dehne","year":"2003","unstructured":"Dehne, F., Fellows, M., Rosamond, F.: An FPT Algorithm for Set Splitting. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 180\u2013191. Springer, Heidelberg (2003)"},{"key":"1_CR21","unstructured":"Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.: Solving Large FPT Problems on Coarse Grained Parallel Machines (2002) (manuscript)"},{"key":"1_CR22","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":"1_CR23","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":"1_CR24","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":"1_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 653\u2013663 (1998)","DOI":"10.1109\/SFCS.1998.743516"},{"key":"1_CR26","unstructured":"Jia, W., Zhang, C., Chen, J.: An Efficient Parameterized Algorithm for Set Splitting. To appear in Journal of Algorithms (2003) (manuscript)"},{"key":"1_CR27","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":"1_CR28","unstructured":"McCartin, C.: Ph.D. dissertation in Computer Science, Victoria University, Wellington, New Zealand (2003)"},{"key":"1_CR29","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Habilitationschrift, University of T\u00fcbingen (2002)"},{"key":"1_CR30","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 shape 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":"1_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/3-540-57155-8_284","volume-title":"Algorithms and Data Structures","author":"J.A. Telle","year":"1993","unstructured":"Telle, J.A., Proskurowski, A.: Practical Algorithms on Partial k-Trees with an Application to Domination-Like Problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 610\u2013621. Springer, Heidelberg (1993)"},{"key":"1_CR32","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":"1_CR33","unstructured":"Weihe, K.: Covering Trains by Stations, or the Power of Data Reduction. In: Proc. ALEX 1998, 1\u20138 (1998)"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Exact Algorithms for NP-hard Problems: A Survey (2003) (manuscript)","DOI":"10.1007\/3-540-36478-1_17"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T13:19:06Z","timestamp":1559567946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}