摘要
最大独立集问题是著名的NP-hard问题,在许多领域都有广泛的实际应用。在给定无向图G=(V,E)中,最大独立集是顶点V的一个子集I,I中顶点的数量最大且任意2个顶点都不相邻。本文提出了一种启发式的最大独立集问题算法RI-DS-TS,本算法由3部分组成:随机初始化,基于度与支撑的顶点挑选,基于禁忌搜索的独立集优化。本文给出了RI-DS-TS算法的具体步骤,并使用DIMACS基准中的实例对RI-DS-TS算法进行了验证,通过和目前已知的最优结果对比,本算法在满足经济性的同时取得了令人满意的效果。
The Maximum Independent Set(MIS)Problem is a classic NP-hard problem with many real world applications.Given a graph G=(V,E),the independent set is the maximum-cardinality subset I of V such that no two vertices in I are adjacent.This paper proposed a heuristic algorithm,RI-DS-TS,to find the maximum independent set of a graph.RI-DS-TS algorithm consists of three parts:random Initialization,vertex selection based on vertex degree and support,independent set optimization based on tabu search.This algorithm is addressed in detail and tested on DIMACS benchmark graphs.Compared with the known best solutions of the instances in DIMACS benchmark,RI-DS-TS algorithm achieves satisfied results with consideration of economy.
作者
冯云
FENG Yun(Hebei Institute for Drug and Medical Device Control,Shijiazhuang Hebei 050081,China)
出处
《河北省科学院学报》
CAS
2021年第3期9-13,共5页
Journal of The Hebei Academy of Sciences
关键词
图论
最大独立集
启发式算法
Graph theory
Maximum independent set
Heuristic algorithm
