A fixed-parameter tractable algorithm for matrix domination
MATRIX DOMINATION is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time O(n(3) + 1.959(k) k(5/2)). (C) 2004 Elsevier B.V. All rights reserved.
computational complexity parameterized complexity graph algorithms analysis of algorithms