一个新的极大独立集算法及独立数的界  

New algorithm of maximal independent set and upper bound of independent number

作　　者：李勤丰[1] 李尤丰[2] 丁根宏[3] 

机构地区：[1]金陵科技学院基础部,南京210001 [2]金陵科技学院信息技术学院,南京210001 [3]河海大学理学院,南京210098

出　　处：《计算机工程与应用》2008年第26期48-50,共3页Computer Engineering and Applications

摘　　要：最大独立集问题是图论中典型的组合优化问题,有着广泛的实际应用价值。分析了现有独立数的界公式后给出了新的上界公式,并通过分析贪婪算法和独立集自身的特征,给出了新的求解极大独立集的算法,并证明了其确定性。然后用实例验证了该算法的有效性。The maximum independent set problem is a classical problem in combinatorial optimization.It has been used widely.Firstly an upper bound is shown.Then by the analysis of the character of the maximum independent sets and the colligation of meta-heuristic algorithm,a new algorithm is given and its assurance is proved.After abundant experiments,the results show adequately that the algorithm presented in the thesis is efficacious.

关 键 词：极大独立集 界 贪婪算法 图论 

分 类 号：O157.6[理学—数学] TP39[理学—基础数学]