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...
Saved in:
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
University of Sindh, Jamshoro, Pakistan
2016
|
Subjects: | |
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 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
my.iium.irep.53856 |
---|---|
record_format |
dspace |
spelling |
my.iium.irep.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 REM 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 |
institution |
Universiti Islam Antarabangsa Malaysia |
building |
IIUM Library |
collection |
Institutional Repository |
continent |
Asia |
country |
Malaysia |
content_provider |
International Islamic University Malaysia |
content_source |
IIUM Repository (IREP) |
url_provider |
http://irep.iium.edu.my/ |
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/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 |
_version_ |
1643614431968493568 |
score |
13.18916 |