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

A NEW HEURISTIC ALGORITHM TO SOLVE THE MAXIMUM INDEPENDENT SET PROBLEM

Sayfa
495–501
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

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

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (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.