A Simple, Fast and Near Optimal Approximation Algorithm for Optimization of Un-Weighted Minimum Vertex Cover
Muhammad Fayaz, Shakeel Arshad, Umar Zaman, Akhlaque Ahmad · 2016
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.