摘要
最大独立集问题是图论中典型的组合优化问题,有着广泛的实际应用价值。分析了现有独立数的界公式后给出了新的上界公式,并通过分析贪婪算法和独立集自身的特征,给出了新的求解极大独立集的算法,并证明了其确定性。然后用实例验证了该算法的有效性。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2008年第26期48-50,共3页
Computer Engineering and Applications
关键词
极大独立集
界
贪婪算法
图论
maximal independent set
bound
greedy algorithm
graph theory
