| 最大顶点覆盖问题的一种近似算法 |
| |
| 引用本文： | 王莲花,杨建雅,王继顺. 最大顶点覆盖问题的一种近似算法[J]. 数学的实践与认识, 2007, 37(19): 194-197 |
| |
| 作者姓名： | 王莲花 杨建雅 王继顺 |
| |
| 作者单位： | 1. 运城学院,应用数学系,山西,运城,044000
2. 连云港师范高等专科学校,数学系,连云港,222006 |
| |
| 摘 要： | 给出了求解最大顶点覆盖问题的一种近似算法,讨论了它的性能保证,利用P ipage技术,为最大顶点覆盖问题设计出了0.75-近似算法.
|
| 关 键 词： | 最大顶点覆盖 近似算法 性能保证 ε-凸性 |
| 修稿时间： | 2007-03-07 |
An Approximate Method for Max-Vertex-Cover |
| |
| WANG Lian-hua,YANG Jian-ya,WANG Ji-shun. An Approximate Method for Max-Vertex-Cover[J]. Mathematics in Practice and Theory, 2007, 37(19): 194-197 |
| |
| Authors: | WANG Lian-hua YANG Jian-ya WANG Ji-shun |
| |
| Abstract: | A new approximate method is presented for max-vertex-cover problem,and its performance guarantee is analyzed.By using the Pipage technique,a 0.75-approximate algorithm is presented. |
| |
| Keywords: | max-vertex-cover approximate method performance guarantee ε-convexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
