| 一种求解平面图的最小顶点覆盖算法 |
| |
| 引用本文： | 吴春,朱国魂,谢玉忠,林宏.一种求解平面图的最小顶点覆盖算法[J].计算机系统应用,2010,19(9):97-100. |
| |
| 作者姓名： | 吴春 朱国魂 谢玉忠 林宏 |
| |
| 作者单位： | 桂林电子科技大学,计算机与控制学院,广西,桂林,541004 |
| |
| 基金项目： | 广西区教育厅立项项目(200911LX114) |
| |
| 摘 要： | 最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。
|
| 关 键 词： | 点覆盖 最小顶点覆盖 最大独立集 平面图 邻域 |
| 收稿时间： | 1/4/2010 12:00:00 AM |
| 修稿时间： | 2010/1/27 0:00:00 |
Minimum Vertex Cover Algorithm for Solving the Planar Graph |
| |
| WU Chun,ZHU Guo-Hun,XIE Yu-Zhong and LIN Hong.Minimum Vertex Cover Algorithm for Solving the Planar Graph[J].Computer Systems& Applications,2010,19(9):97-100. |
| |
| Authors: | WU Chun ZHU Guo-Hun XIE Yu-Zhong and LIN Hong |
| |
| Affiliation: | (School of Computer and Control, Guilin University of Electronic and Technology, Guilin 541004, China) |
| |
| Abstract: | The minimum vertex cover problem is a classical problem in combinatorial optimization and has a wide range of values in real life. The problem of the minimum vertex cover and the maximum independent set is actually the equivalence problem in the graph theory. In this paper, the maximum independent set angle and design a maximum independent set algorithm for solving the planar graph is formed, according to characteristics of the maximum independent set, and then the minimum vertex cover is obtained. After many experiments, the results show adequately that the algorithm presented in the thesis is correct and effective. |
| |
| Keywords: | vertex cover minimum vertex cover maximum independent set planar graph epsilon neighborhood |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机系统应用》浏览原始摘要信息 |
|
点击此处可从《计算机系统应用》下载全文 |
|
