| 分层算法求解竞赛图上的最小弱顶点覆盖 |
| |
| 引用本文： | 赖文华,涂建华.分层算法求解竞赛图上的最小弱顶点覆盖[J].北京化工大学学报(自然科学版),2012,39(1):103-105. |
| |
| 作者姓名： | 赖文华 涂建华 |
| |
| 作者单位： | 北京化工大学理学院,北京,100029;北京化工大学理学院,北京,100029 |
| |
| 基金项目： | 中央高校基本科研业务费(ZZ1133) |
| |
| 摘 要： | 竞赛图上的弱顶点覆盖问题是一个NP困难问题，本文先定义了竞赛图上的势加权函数，然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法，并证明了此近似算法的近似度为3
|
| 关 键 词： | 竞赛图 弱顶点覆盖 分层算法 势加权函数 |
Layer algorithm for the minimum weak vertex cover problem in tournaments |
| |
| LAI WenHua TU JianHua.Layer algorithm for the minimum weak vertex cover problem in tournaments[J].Journal of Beijing University of Chemical Technology,2012,39(1):103-105. |
| |
| Authors: | LAI WenHua TU JianHua |
| |
| Institution: | School of Science, Beijing University of Chemical Technology, Beijing 100029, China |
| |
| Abstract: | The problem of finding a weak vertex cover set with the minimum total weight in a weighted tournament has been shown to be NP-hard.In this paper,we first define the power weighted function in tournaments,and then using layering technology,we give a factor 3 approximation algorithm for the minimum weak vertex cover problem in tournaments. |
| |
| Keywords: | tournament weak vertex cover layer algorithm power weighted function |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《北京化工大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《北京化工大学学报(自然科学版)》下载免费的PDF全文 |
