Parameterized complexity: Difference between revisions

Revision as of 14:25, 17 February 2006

Revision as of 17:22, 15 March 2006

Line 10:

For example there is an algorithm which solves the vertex cover problem in <math>O(kn + 1.29^k)</math> time, where <math>n</math> is the number of vertices and <math>k</math> is the size of the vertex cover. This proves that vertex cover is fixed-parameter tractable with respect to this parameter.

==References==

*{{cite book

| first=Rod

| last=Downey

| coauthors=M. Fellows

| title=Parameterized complexity

| publisher=Springer

| year=1997

| url=http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X

}} ISBN 0-387-94883-X

[[Category:Computational complexity theory]]