A Simple, Fast and Near Optimal Approximation Algorithm for Optimization of Un-Weighted Minimum Vertex Cover

Fayaz M., Arshad S., Zaman U., Ahmad A.

14th International Conference on Frontiers of Information Technology, FIT 2016, Islamabad, Pakistan, 19 - 21 Aralık 2016, ss.176-180 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/fit.2016.040
  • Basıldığı Şehir: Islamabad
  • Basıldığı Ülke: Pakistan
  • Sayfa Sayıları: ss.176-180
  • Anahtar Kelimeler: Approximation algorithm, Maximum independent set problem, Minimum vertex cover problem, NP-problem, Optimal
  • TED Üniversitesi Adresli: Hayır

Özet

© 2016 IEEE.This paper presents a simple and efficient near optimal algorithm, named Maximum Adjacent Minimum degree Algorithm (MAMA) for optimization of minimum vertex cover problem. The proposed algorithm at each step add that maximum degree vertex which is adjacent to minimum degree vertex. The computational complexity and optimality comparison are carried with other state of the art algorithms on small benchmark instances as well as on large benchmark instances to check the efficiency of the proposed algorithm. The proposed algorithm outperforms the other well-known algorithm and returns near optimal result in quick time.