I'm not sure if Column/Row "Covering" is the correct terminology.

I have a square matrix. I would like to know how to determine the minimum number of lines (rows and/or columns) needed to "cover" the zero elements.

For example, given this:

2 0 0 5
4 4 0 9
6 0 0 5
9 3 0 3

I could cover the zeros by drawing a line through each row, requiring 4 lines. On the other hand, if I were to draw a line through rows 1 and 3 and column 3, I would only need 3 lines. If I were to draw a line through columns 2 and 3 I would only need two lines.

Of course, in this simple 4x4 it's easy to visually inspect and see the correct solution.

First, I'd like to know if there is a term for what I am trying to do. I feel this must be a common operation. What is the name of the thing I am trying to determine? Second, what is the best algorithm for doing so?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.