Cover Image

Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review

In this paper, a detailed literature review and comparative analysis, based on simplicity, efficiency and the run-time complexity of some well known approximation algorithms for Minimum Vertex Cover (MVC) problem have been carried out. The key contribution of this paper is the provision of small ben...

Full description

Saved in:
Bibliographic Details
Main Authors: Fayaz, Muhammad, Arshad, Shakeel, Shah, Abdul Salam, Shah, Asadullah
Format: Article
Language:English
English
Published: Science and Engineering Research Support Society (SERSC) 2018
Subjects:
T10.5 Communication of technical information
Online Access:http://irep.iium.edu.my/62522/7/62522%20Approximate%20methods%20for%20minimum%20vertex%20cover%20fail%20to%20provide%20optimal%20results%20SCOPUS.pdf
http://irep.iium.edu.my/62522/13/62522_Approximate%20methods%20for%20minimum%20vertex%20cover%20fail%20to%20provide%20optimal%20results%20on%20small%20graph%20instances.pdf
http://irep.iium.edu.my/62522/
http://www.sersc.org/journals/IJCA/vol11_no2.php
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.iium.irep.62522
record_format dspace
spelling my.iium.irep.625222018-07-30T08:26:35Z http://irep.iium.edu.my/62522/ Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review Fayaz, Muhammad Arshad, Shakeel Shah, Abdul Salam Shah, Asadullah T10.5 Communication of technical information In this paper, a detailed literature review and comparative analysis, based on simplicity, efficiency and the run-time complexity of some well known approximation algorithms for Minimum Vertex Cover (MVC) problem have been carried out. The key contribution of this paper is the provision of small benchmark graphs on which the given approximation algorithms fail to provide optimal results. The small benchmark graphs will help the researchers to evaluate efficient approximation algorithms. Generally, different terminologies and different styles have been adopted for writing pseudo code for different algorithms. To avoid such kind of difficulties, a uniform set of terminologies and pseudo code for each algorithm is provided in this paper, which will help researchers to easily understand the approximation algorithm for Minimum Vertex Cover (MVC) problem. Science and Engineering Research Support Society (SERSC) 2018 Article PeerReviewed application/pdf en http://irep.iium.edu.my/62522/7/62522%20Approximate%20methods%20for%20minimum%20vertex%20cover%20fail%20to%20provide%20optimal%20results%20SCOPUS.pdf application/pdf en http://irep.iium.edu.my/62522/13/62522_Approximate%20methods%20for%20minimum%20vertex%20cover%20fail%20to%20provide%20optimal%20results%20on%20small%20graph%20instances.pdf Fayaz, Muhammad and Arshad, Shakeel and Shah, Abdul Salam and Shah, Asadullah (2018) Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review. International Journal of Control and Automation, 11 (2). pp. 135-150. ISSN 2005-4297 http://www.sersc.org/journals/IJCA/vol11_no2.php
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
English
topic T10.5 Communication of technical information
spellingShingle T10.5 Communication of technical information
Fayaz, Muhammad
Arshad, Shakeel
Shah, Abdul Salam
Shah, Asadullah
Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review
description In this paper, a detailed literature review and comparative analysis, based on simplicity, efficiency and the run-time complexity of some well known approximation algorithms for Minimum Vertex Cover (MVC) problem have been carried out. The key contribution of this paper is the provision of small benchmark graphs on which the given approximation algorithms fail to provide optimal results. The small benchmark graphs will help the researchers to evaluate efficient approximation algorithms. Generally, different terminologies and different styles have been adopted for writing pseudo code for different algorithms. To avoid such kind of difficulties, a uniform set of terminologies and pseudo code for each algorithm is provided in this paper, which will help researchers to easily understand the approximation algorithm for Minimum Vertex Cover (MVC) problem.
format Article
author Fayaz, Muhammad
Arshad, Shakeel
Shah, Abdul Salam
Shah, Asadullah
author_facet Fayaz, Muhammad
Arshad, Shakeel
Shah, Abdul Salam
Shah, Asadullah
author_sort Fayaz, Muhammad
title Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review
title_short Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review
title_full Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review
title_fullStr Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review
title_full_unstemmed Approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: A review
title_sort approximate methods for minimum vertex cover fail to provide optimal results on small graph instances: a review
publisher Science and Engineering Research Support Society (SERSC)
publishDate 2018
url http://irep.iium.edu.my/62522/7/62522%20Approximate%20methods%20for%20minimum%20vertex%20cover%20fail%20to%20provide%20optimal%20results%20SCOPUS.pdf
http://irep.iium.edu.my/62522/13/62522_Approximate%20methods%20for%20minimum%20vertex%20cover%20fail%20to%20provide%20optimal%20results%20on%20small%20graph%20instances.pdf
http://irep.iium.edu.my/62522/
http://www.sersc.org/journals/IJCA/vol11_no2.php
_version_ 1643617369914867712
score 13.211869

Similar Items