Fixed-parameter tractability and completeness. I: Basic results. (English) Zbl 0830.68063

Downey, Rod G.; Fellows, Michael R.

SIAM J. Comput. 24, No. 4, 873-921 (1995).

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15	Complexity of computation (including implicit computational complexity)
03D10	Turing machines and related notions
03D20	Recursive functions and relations, subrecursive hierarchies
03D30	Other degrees and reducibilities in computability and recursion theory
03D80	Applications of computability and recursion theory
68R10	Graph theory (including graph drawing) in computer science

Keywords:

fixed-parameter problems; fixed-parameter tractability