An Exact Algorithm Based on Chain Indication for Min-CVCB Problem

With the technical development of VLSI （very large scale integrated circuit）, the constrained minimum vertex cover in bipartite graphs （Min-CVCB） for re-configurable arrays has attracted considerable attention in the literature. The Min-CVCB problem is a classical sub-problem of vertex cover problem, and has been proved to be NP-complete. At present, the best exact algorithm for the problem is proposed by using kernelization and branching technology with running time bounded by O（（k\-u+k\-l）|G|+1.26\+\k\-u+k\-l\）, which is still unable to satisfy the requirement of the industry development. Based on the above result, an improved parameterized algorithm is presented for the Min-CVCB problem. For the Min-CVCB problem, a more detailed analysis is given for the structure of the bipartite graph and list all the possible joint of the blocks whose weight are at least 3 in a case-by-case exhaustive manner. Based on the above analysis, full use is made of the chain implication and bounded searching technology is used to construct new recurrence relations. For the remaining blocks generated by branching, dynamic programming technology is used to handle, which can be solved in polynomial time. The total time complexity of this algorithm is bounded by O（（k\-u+k\-l）|G|+1.1892\+\k\-u+k\-l\）, which greatly improves the current best result.