一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法  

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

作　　者：许小双[1] 王建新[1] 刘云龙[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2007年第6期270-273,282,共5页Computer Science

基　　金：国家自然科学基金重点项目:生物信息学中的相关组合理论和算法研究(60433020)。

摘　　要：二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。Constrained minimum vertex cover in bipartite graphs （Min-CVCB）problem is a NP-complete problem, it can＇t be solved in polynomial time, unless P= NP. In this paper, we provide an approximation algor/thm which is based on chain implication to solve this problem. When the instance of Min-CVCB problem has a minimum vertex cover （ku, kt ）, for any given constant,δ=1＋ε〉1,, we can get a constrained approximate vertex cover （ku,kl）, the approximation ratio is maxmax{ku^＊/ku,kl^＊/kl}≤1＋ε, and the algorithm runs in time O（22/ε）. Obviously, it is a polynomial time approximation scheme for the Min-CVCB problem.

关 键 词：二分图的受约束最小点覆盖 近似算法 参数计算 PTAS算法 

分 类 号：O153.1[理学—数学]