A New Heuristic Algorithm to Solve the Maximum Independent Set Problem

Mathematical and Computational Applications

Ugurlu, Onur¹ 

关键词: maximum independent set problem;    heuristics algorithms;    optimization;    NP-hard problems;   

DOI  :  10.3390/mca18030495

学科分类：计算数学

来源: mdpi

【 摘 要 】

The Maximum Independent Set Problem is a classic graph optimization NPhard problem. Given a graph G=(V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. In this paper, the maximum independent set problem is discussed and a new heuristic algorithm is proposed to solve this problem. The performance of the algorithm has been tested on DIMACS benchmark instances and compared with the literature works. The experimental results show that the proposed approach can yield good solutions.

【 授权许可】

CC BY