Parameterized complexity: Difference between revisions

Revision as of 17:34, 2 July 2010

Revision as of 08:37, 3 July 2010

Line 17:

For example, there is an algorithm which solves the vertex cover problem in <math>O(kn + 1.274^k)</math> time, where <math>n</math> is the number of vertices and <math>k</math> is the size of the vertex cover. This means that vertex cover is fixed-

parameter tractable with the size of the solution as the only parameter.

==W hierarchy==