| 一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法 |
| |
| 引用本文： | 许小双,王建新,刘云龙,陈建二.一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法[J].计算机科学,2007,34(6):270-273. |
| |
| 作者姓名： | 许小双 王建新 刘云龙 陈建二 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 摘 要： | 二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为：当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖（ku,kl）时,对任意给定的近似率δ=1＋ε〉1,一定可以找到一个受约束近似点覆盖（ku,kl）,对应的近似率为max{ku^＊/ku,kl^＊/kl}≤1＋ε,整个近似算法的运行时间复杂度为O（22/ε）。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案（polynomial time approximation scheme,PTAS算法）。
|
| 关 键 词： | 二分图的受约束最小点覆盖 近似算法 参数计算 PTAS算法 |
An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Cover in Bipartite Graphs |
| |
| XU Xiao-Shuang,WANG Jian-Xin,LIU Yun-Long,CHEN Jian-Er.An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Cover in Bipartite Graphs[J].Computer Science,2007,34(6):270-273. |
| |
| Authors: | XU Xiao-Shuang WANG Jian-Xin LIU Yun-Long CHEN Jian-Er |
| |
| Affiliation: | School of Information Science and Engineering,Central South University,Changsha 410083 |
| |
| Abstract: | |
| |
| Keywords: | Constrained minimum vertex cover in bipartite graphs Approximation algorithm Parameterized computation Polynomial time approximation scheme |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
|
