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

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

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

Full description

Bibliographic Details
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/
http://irep.iium.edu.my/53856/
http://irep.iium.edu.my/53856/1/An%20Optimal%20Approximation%20Algorithm%20for%20Optimization%20of%20Un-Weighted%20Minimum%20Vertex%20Cover%20Problem.pdf
id iium-53856
recordtype eprints
spelling iium-538562017-03-13T08:39:35Z http://irep.iium.edu.my/53856/ An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem Fayaz, Muhammad Arshad, S Shah, Abdul Salam Shah, Asadullah QA75 Electronic computers. Computer science 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. University of Sindh, Jamshoro, Pakistan 2016 Article PeerReviewed application/pdf en http://irep.iium.edu.my/53856/1/An%20Optimal%20Approximation%20Algorithm%20for%20Optimization%20of%20Un-Weighted%20Minimum%20Vertex%20Cover%20Problem.pdf 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 http://sujo.usindh.edu.pk/index.php/SURJ/index
repository_type Digital Repository
institution_category Local University
institution International Islamic University Malaysia
building IIUM Repository
collection Online Access
language English
topic QA75 Electronic computers. Computer science
spellingShingle QA75 Electronic computers. Computer science
Fayaz, Muhammad
Arshad, S
Shah, Abdul Salam
Shah, Asadullah
An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
description 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.
format Article
author Fayaz, Muhammad
Arshad, S
Shah, Abdul Salam
Shah, Asadullah
author_facet Fayaz, Muhammad
Arshad, S
Shah, Abdul Salam
Shah, Asadullah
author_sort Fayaz, Muhammad
title An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
title_short An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
title_full An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
title_fullStr An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
title_full_unstemmed An optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
title_sort optimal approximation algorithm for optimization of un-weighted minimum vertex cover problem
publisher University of Sindh, Jamshoro, Pakistan
publishDate 2016
url http://irep.iium.edu.my/53856/
http://irep.iium.edu.my/53856/
http://irep.iium.edu.my/53856/1/An%20Optimal%20Approximation%20Algorithm%20for%20Optimization%20of%20Un-Weighted%20Minimum%20Vertex%20Cover%20Problem.pdf
first_indexed 2023-09-18T21:16:11Z
last_indexed 2023-09-18T21:16:11Z
_version_ 1777411577671057408

Similar Items