| 寻找最大独立集的算法 |
| |
| 引用本文： | 郭廷花.寻找最大独立集的算法[J].太原师范学院学报(自然科学版),2014(2):26-28. |
| |
| 作者姓名： | 郭廷花 |
| |
| 作者单位： | 山西金融职业学院基础部,山西太原030008 |
| |
| 摘 要： | 提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向.
|
| 关 键 词： | 图密度 最大独立集 局部搜索 贪婪思想 |
An Algorithm for Finding Maximum Independent Set in a Graph |
| |
| Guo Tinghua.An Algorithm for Finding Maximum Independent Set in a Graph[J].Journal of Taiyuan Normal University:Natural Science Edition,2014(2):26-28. |
| |
| Authors: | Guo Tinghua |
| |
| Institution: | Guo Tinghua (Shanxi Professional College of Finance,Taiyuan 030008,China) |
| |
| Abstract: | To present two local search algorithms for finding maximum independent set in a graph.It bases on a greedy thought.Through testing,the second is better the first algorithm in sparse graphs.Because of the defect of the local search algorithm,it is studied that we modify the neighborhood function and select vertex in the future. |
| |
| Keywords: | graph density maximum independent local search greedy thought |
| 本文献已被 CNKI 维普 等数据库收录！ |
