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

Fayaz, Muhammad and Arshad, S and Shah, Abdul Salam and Shah, Asadullah (2016) An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem. SINDH university Research Journal ( science series ), 48 (4D). pp. 175-182. ISSN 1813-1743

PDF - Published Version Restricted to Repository staff only Download (336kB) | Request a copy

Abstract

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.

Item Type:	Article (Journal)
Additional Information:	6566/53856
Uncontrolled Keywords:	Approximation algorithm, modified Vertex support algorithm (MVSA), maximum independent set (MIS),minimum Vertex cover (MVC), Vertex cover (VC), Vertex support algorithm (VSA)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Fardous Mohamed Ali Eljadi
Date Deposited:	03 Jan 2017 10:24
Last Modified:	13 Mar 2017 16:39
URI:	http://irep.iium.edu.my/id/eprint/53856

Actions (login required)

View Item