欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
偶图(Min-CVCB 问题) 上的抑制最小的顶点覆盖问题是一个重要 NP 完全的问题。这篇论文基于链牵连的技术为这个问题论述一个多项式时间近似算法。为任何给定的经常的 ɛ 】 0 ，如果 Min-CVCB 问题的一个例子有尺寸的一个最小的顶点封面( k u , k l ),我们的算法构造尺寸的一个顶点封面( k * u , k * l ),令人满意的最大{ k * u /k u , k * l /k l } ≤ 1 + ɛ。这篇文章的联机版本(做 i：10.1007/s11390-008-9180-5 ) 包含增补材料，它对授权用户可得到。
英文摘要：
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 ＋ ε.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
期刊信息
位置：