计算机工程与应用2026，Vol.62Issue(15)：66-86,21.DOI:10.3778/j.issn.1002-8331.2510-0186
最大独立集问题的算法研究综述
Review of Algorithms for Maximum Independent Set Problems
摘要
Abstract
The maximum independent set problem is a typical NP-hard combinatorial optimization problem,widely applied in fields such as wireless network design,social network analysis,resource allocation,and graph mining.Due to its high computational complexity,researchers have proposed various heuristic,intelligent optimization,and machine learning approaches to obtain high-quality approximate solutions for different graph structures and application requirements.Cen-tered on the development of MIS research,existing studies can be categorized into three main paradigms—heuristic algo-rithms,intelligent optimization algorithms,and machine learning based algorithms—which are systematically analyzed in terms of their underlying principles,improvement strategies,performance,and solution accuracy.The advantages and lim-itations of each approach are summarized,their applicability to different graph structures and scales is discussed,and future research trends and algorithm design directions are further explored.关键词
最大独立集/智能优化算法/启发式算法Key words
maximum independent set/intelligent optimization algorithm/heuristic algorithm分类
信息技术与安全科学引用本文复制引用
颜冬,王晓峰,锁小娜,胡思敏,宋家欢..最大独立集问题的算法研究综述[J].计算机工程与应用,2026,62(15):66-86,21.基金项目
宁夏自然科学基金(2024AAC03165,2024AAC03169) （2024AAC03165,2024AAC03169）
宁夏青年拔尖人才项目(2021). （2021）
