The experimental results show that the proposed approach can yield good solutions.
📌 3 Maddede Bu Makale
🎯
Amaç & Hipotez:The Maximum Independent Set Problem is a classic graph optimization NPhard problem.
📊
Temel Bulgular & Veri:The performance of the algorithm has been tested on DIMACS benchmark instances and compared with the literature works.
💡
Sonuç & Katkı:The experimental results show that the proposed approach can yield good solutions.
🔬Tür:Modelleme & Sayısal Simülasyon
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri
Abstract
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.
🔖
Bu Makaleye Atıf Yap
UĞURLU, O. (2013). A NEW HEURISTIC ALGORITHM TO SOLVE THE MAXIMUM INDEPENDENT SET PROBLEM. Mathematical and Computational Applications, Cilt: 18 - Sayı: 3, 495–501. https://ajindex.com/articles/279805
M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory NP-completeness, San Francisco: Freeman, 1979
S. Balaji, V. Swaminathan, K. Kannan, Simple Algorithm to Optimize Maximum Independent Set, Advanced Modeling and Optimization 12(1), 2010
T. H. Cormen, C. E. Lieserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition, The MIT Press, 2001
L. E. Gibbons, D. W. Hearn and P. M. Pardalos, A Continuous Based Heuristic for the Maximum Clique Problem, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, 103-124, 1994
S. Busgin, S. Butenko and P. M. Pardalos, A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere, Journal of Combinatorial Optimization 6, 287-297, 2002
E. Loukakis and C. Tsouros, Determining the Number of Internal Stability of a Graph, Journal of Computational Mathematics 11, 232-248, 1982
R. Carraghan and P. M. Pardalos, An Exact Algorithm for the Maximum Clique Problem, Operation Research Letter 9, 375-38, 19908. P. M. Pardalos and J. Xue, The Maximum Clique Problem, Journal of Global Optimization 4, 301-328, 1994
V. C. Barbosa and L. C. D. Campos, A Novel Evolutionary Formulation of the Independent Set Problem, 2008
R. Boppana and M. M. Halldorsson, Approximating Maximum Independent Set by Excluding Subgraphs, Bit Numerical Mathematics 32, 180-196, 1992
E. Balas and C. S. Yu, Finding the Maximum Clique in an Arbitrary Graph, SIAM Journal on Computing 15, 1054-1068, 1986
C. Bron and J. Kerbosch, Finding All Cliques of an Undirected Graph, Communications of the ACM 16, 575-577, 1973
DIMACS clique benchmarks, Benchmark instances made available by electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ. 1993.