Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs  

作　　者：王建新 许小双 陈建二 

机构地区：[1]School of Information Science and Engineering, Central South University [2]Department of Computer Science, Texas A & M University, College Station

出　　处：《Journal of Computer Science & Technology》2008年第5期763-768,共6页计算机科学技术学报（英文版）

基　　金：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.

摘　　要：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 ＋ ε.

关 键 词：Min-CVCB parameter complexity chain implication approximation algorithm 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]