Abstract
This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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. 2368, pp. 150–159. Springer, Heidelberg (2002)
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. 2136, pp. 111–122. Springer, Heidelberg (2001)
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)
Alber, J., Niedermeier, R.: Improved Tree Decomposition Based Algorithms for Domination-Like Problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 613–627. Springer, Heidelberg (2002)
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–12 (1996)
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–563. IEEE Press, Los Alamitos (1997)
Bonsma, P.S., Brüggemann, T., Woeginger, G.J.: A faster FPT algorithm for finding spanning trees with many leaves (2003) (manuscript)
Bodlaender, H.L.: On Linear Time Minor Tests and Depth-First Search. Journal of Algorithms 14, 1–23 (1993)
Bodlaender, H.L.: A Linear Time Algorithm for Finding Tree- Decompositions of Small Treewidth. SIAM Journal on Computing 25, 1305–1317 (1996)
Cai, L., Chen, J., Downey, R., Fellows, M.: On the Parameterized Complexity of Short Computation and Factorization. Archive for Mathematical Logic 36, 321–337 (1997)
Chor, B., Fellows, M., Juedes, D.: An Efficient FPT Algorithm for Saving k Colors (2003) (manuscript)
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. 2076, pp. 273–284. Springer, Heidelberg (2001)
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–222 (2000)
Cesati, M., Trevisan, L.: On the Efficiency of Polynomial Time Approximation Schemes. Information Processing Letters 64, 165–171 (1997)
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–218 (2003)
Downey, R.G., Fellows, M.R.: Parameterized Computational Feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, Birkhauser, Boston, pp. 219–244 (1995)
Downey, R.G., Fellows, M.R.: Fixed Parameter Tractability and Completeness II: Completeness for W[1]. Theoretical Computer Science A 141, 109–131 (1995)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Downey, R., Fellows, M., Prieto-Rodriguez, E., Rosamond, F.: Fixed-parameter Tractability and Completeness V: Parametric Miniatures (2003) (manuscript)
Dehne, F., Fellows, M., Rosamond, F.: An FPT Algorithm for Set Splitting. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 180–191. Springer, Heidelberg (2003)
Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.: Solving Large FPT Problems on Coarse Grained Parallel Machines (2002) (manuscript)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial Time Approximation Schemes for Geometric Graphs. In: Proc. ACM Symposium on Discrete Algorithms (SODA 2001), pp. 671–679. ACM Press, New York (2001)
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 5, 117–126
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. 1974, pp. 240–251. Springer, Heidelberg (2000)
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–663 (1998)
Jia, W., Zhang, C., Chen, J.: An Efficient Parameterized Algorithm for Set Splitting. To appear in Journal of Algorithms (2003) (manuscript)
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. 1858, pp. 137–147. Springer, Heidelberg (2000)
McCartin, C.: Ph.D. dissertation in Computer Science, Victoria University, Wellington, New Zealand (2003)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Habilitationschrift, University of Tübingen (2002)
Prieto, E., Sloper, C.: Either/Or: Using vertex cover structure in designing FPT-algorithms — the case of shape k-Internal Spanning Tree. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 474–483. Springer, Heidelberg (2003)
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. 709, pp. 610–621. Springer, Heidelberg (1993)
Shamir, R., Tzur, D.: The Maximum Subforest Problem: Approximation and Exact Algorithms. In: Proc. ACM Symposium on Discrete Algorithms (SODA 1998), pp. 394–399. ACM Press, New York (1998)
Weihe, K.: Covering Trains by Stations, or the Power of Data Reduction. In: Proc. ALEX 1998, 1–8 (1998)
Woeginger, G.J.: Exact Algorithms for NP-hard Problems: A Survey (2003) (manuscript)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fellows, M.R. (2003). Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT . In: Bodlaender, H.L. (eds) Graph-Theoretic Concepts in Computer Science. WG 2003. Lecture Notes in Computer Science, vol 2880. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39890-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-39890-5_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20452-7
Online ISBN: 978-3-540-39890-5
eBook Packages: Springer Book Archive