A fixed-parameter tractable algorithm for matrix domination |
| |
| Authors: | Mark Weston |
| |
| Affiliation: | Department of Computer Science, University of Victoria, P.O. Box 3055, Victoria, BC, Canada |
| |
| Abstract: | 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  . |
| |
| Keywords: | Computational complexity Parameterized complexity Graph algorithms Analysis of algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
