A bipartite graph is an undirected graph whose vertices can be partitioned into two sets of vertices, X and Y, with the properties that no two vertices in each set are adjacent. A vertex cover of a bipartite graph is a set of vertices V such that at l...
A bipartite graph is an undirected graph whose vertices can be partitioned into two sets of vertices, X and Y, with the properties that no two vertices in each set are adjacent. A vertex cover of a bipartite graph is a set of vertices V such that at least one of two vertices incident to each edge is contained in V. A vertex cover is minimum if there is no other vertex cover whose size is smaller. A constrained vertex cover is a vertex cover such that |V∩X|≤r and |V∩Y|≤c for given constants r and c. It is known that the problem of finding constrained minimum vertex cover of a bipartite graph is NP-hard.
In this study, we have developed greedy heuristics and genetic algorithm for the constrained minimum vertex cover problem of a bipartite graph. Our heuristics can be used for the problem of determining whether a redundant random access memory containing faulty cells can be repaired with spare rows and columns.