Journals / Mathematical and Computational Applications / 2013 / Cilt: 18 - Sayı: 3

A NEW HEURISTIC ALGORITHM TO SOLVE THE MAXIMUM INDEPENDENT SET PROBLEM

Pages
495–501
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The experimental results show that the proposed approach can yield good solutions.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The Maximum Independent Set Problem is a classic graph optimization NPhard problem.
📊
Key Findings & Data:The performance of the algorithm has been tested on DIMACS benchmark instances and compared with the literature works.
💡
Conclusion & Impact:The experimental results show that the proposed approach can yield good solutions.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

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.

🔖

Cite This Article

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

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (12)

  1. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory NP-completeness, San Francisco: Freeman, 1979
  2. S. Balaji, V. Swaminathan, K. Kannan, Simple Algorithm to Optimize Maximum Independent Set, Advanced Modeling and Optimization 12(1), 2010
  3. T. H. Cormen, C. E. Lieserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition, The MIT Press, 2001
  4. 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
  5. 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
  6. E. Loukakis and C. Tsouros, Determining the Number of Internal Stability of a Graph, Journal of Computational Mathematics 11, 232-248, 1982
  7. 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
  8. V. C. Barbosa and L. C. D. Campos, A Novel Evolutionary Formulation of the Independent Set Problem, 2008
  9. R. Boppana and M. M. Halldorsson, Approximating Maximum Independent Set by Excluding Subgraphs, Bit Numerical Mathematics 32, 180-196, 1992
  10. E. Balas and C. S. Yu, Finding the Maximum Clique in an Arbitrary Graph, SIAM Journal on Computing 15, 1054-1068, 1986
  11. C. Bron and J. Kerbosch, Finding All Cliques of an Undirected Graph, Communications of the ACM 16, 575-577, 1973
  12. DIMACS clique benchmarks, Benchmark instances made available by electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ. 1993.