摘要
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 ＋ ε.
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 60773111
the National Basic Research 973 Program of China under Grant No. 2008CB317107
the Provincial Natural Science Foundation of Hunan under Grant No. 06JJ10009
the 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.
