最大独立集问题的算法研究综述OA

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.