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 December 2016, pp.176-180 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/fit.2016.040
  • City: Islamabad
  • Country: Pakistan
  • Page Numbers: pp.176-180
  • Keywords: Approximation algorithm, Maximum independent set problem, Minimum vertex cover problem, NP-problem, Optimal
  • TED University Affiliated: No


© 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.