The constrained minimum vertex cover problem on bipartite graphs （the Min-CVCB problem） is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the...The constrained minimum vertex cover problem on bipartite graphs （the Min-CVCB problem） is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε〉 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size （ku, kl）, our algorithm constructs a vertex cover of size （ku^＊, kl^＊）, satisfying max{ku^＊/ku, kl^＊/kl} ≤ 1 ＋ ε.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos. 60433020 and 60773111the National Basic Research 973 Program of China under Grant No. 2008CB317107+2 种基金the Provincial Natural Science Foundation of Hunan under Grant No. 06JJ10009the Program for New Century Excellent Talents in University under Grant No. NCET-05-0683 the Program for Changjiang Scholars and Innovative Research Team in University under Grant No.IRT0661.
文摘The constrained minimum vertex cover problem on bipartite graphs （the Min-CVCB problem） is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε〉 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size （ku, kl）, our algorithm constructs a vertex cover of size （ku^＊, kl^＊）, satisfying max{ku^＊/ku, kl^＊/kl} ≤ 1 ＋ ε.
