The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem), with important applications in the study of reconfigurable arrays in VLSI design, is an NP-hard problem and has attracted considerable attention in the literature. Based on a deeper and more careful analysis on the structures of bipartite graphs, we develop an exact algorithm of running time , which improves the best previous algorithm of running time for the problem.
展开▼
