A New Heuristic Algorithm to Solve the Maximum Independent Set Problem
Makaleler > Tam Makale · 2013
Yazarlar: Onur Ugurlu
Mathematical and Computational Applications, Uluslararası, Scopus, 2013, cilt 18, ss 495-501
DOI: 10.3390/mca18030495
Özet
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.