寻找最大独立集的算法

An Algorithm for Finding Maximum Independent Set in a Graph

提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向.

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.