1
$\begingroup$

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?

$\endgroup$

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.