An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem

• Main Authors: Fayaz, Muhammad, Arshad, S, Shah, Abdul Salam, Shah, Asadullah
• Format: Article
• Language: English
• Published: University of Sindh, Jamshoro, Pakistan 2016
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://irep.iium.edu.my/53856/1/An%20Optimal%20Approximation%20Algorithm%20for%20Optimization%20of%20Un-Weighted%20Minimum%20Vertex%20Cover%20Problem.pdf; http://irep.iium.edu.my/53856/; http://sujo.usindh.edu.pk/index.php/SURJ/index

Mean of Neighbors of Minimum Degree Algorithm (MNMA) is proposed in this paper. The MNMA produces optimal or near optimal vertex cover for any known undirected, un-weighted graph. The MNMA adds a vertex cover at each step among those vertices which are neighbors of minimum degree vertices having degree equal to the mean value to construct vertex cover. The performance of MNMA is compared with other algorithms on small benchmark instances as well as on large benchmark instances such as BHOLIB and DIMACS. The MNMA is an efficient and fast algorithm and outperformed all the algorithms.