| 顶点覆盖问题的贪心算法的设计与分析 |
| |
| 引用本文： | 姚朝灼.顶点覆盖问题的贪心算法的设计与分析[J].福州大学学报(自然科学版),2001,29(1):8-11. |
| |
| 作者姓名： | 姚朝灼 |
| |
| 作者单位： | 福州大学计算机科学与技术系, |
| |
| 摘 要： | 设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 .
|
| 关 键 词： | 顶点覆盖 贪心算法 NP—困难 |
| 文章编号： | 1000-2243(2001)01-0008-04 |
| 修稿时间： | 2000年5月9日 |
Design and analysis of vertex covered problem by greedy algorithm |
| |
| YAO Chao-zhuo.Design and analysis of vertex covered problem by greedy algorithm[J].Journal of Fuzhou University(Natural Science Edition),2001,29(1):8-11. |
| |
| Authors: | YAO Chao-zhuo |
| |
| Institution: | YAO Chao-zhuo (Department of Computer Science and Technology, Fuzhou University, Fuzhou, Fujian 35002, China) |
| |
| Abstract: | As the relative rate η≤2 between such approximate solution andexact solution, this paper introduces another greedy algorithm to solve the problem，and proves the relative rate η≤H(d)， H(d)= ∑1/j (j=(1， 2， ……， d)， where d is the maximal degree of vertex in the graph. Therefore，greedy algorithm has improved the accuracy of solution evidently while d≤3. |
| |
| Keywords: | vertex covered greedy algorithm NP-hard |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 |
