1
$\begingroup$

We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.

example

0 0 1 0

0 1 0 1

0 0 1 0

0 0 1 0

cover 3rd column and 2nd raw. so two plates.

$\endgroup$
2
$\begingroup$

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ with an edge. Now we have a bipartite graph $G=((R,C), V)$, since there is no edge between two rows nor between two columns.

A vertex cover of $G$ corresponds to a set of selected rows and columns such that each matrix entry of 1 is in at least one of selected rows or columns. So, the problem to find minimum number of covering plates is the same as determining the minimum vertex cover for graph $G$.

Thanks to Kőnig's theorem, for bipartite graph $G$, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. So, the problem is shifted to find a a maximum-cardinality matching of $G$.

There are many efficient algorithms that finds a maximum-cardinality matching in a bipartite graph, such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. There are many existing implementations of them in various programming languages that can be easily searched.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.