Parameterized complexity after (almost) ten years: Review and open questions. (English) Zbl 0961.68533

Downey, Rodney G.; Fellows, Michael R.

Calude, C. S. (ed.) et al., Combinatorics, computation & logic. Proceedings of DMTCS ’99 and CATS ’99. Auckland, New Zealand, January 18-21, 1999. Singapore: Springer. Aust. Comput. Sci. Commun. 21, 3, 1-33 (1999).

Summary: We give a review of the development and some of the achievements of the theory of parameterized complexity in the last (nearly) ten years. We highlight what we see as some of the major open questions and programs for future development.
For the entire collection see [Zbl 0932.00058].

MSC:

68R10	Graph theory (including graph drawing) in computer science
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

parameterized complexity