IIUM Repository

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

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 E-ISSN 2207-6387

[img] PDF (SCOPUS) - Supplemental Material
Restricted to Registered users only

Download (504kB) | Request a copy
[img] PDF - Published Version
Restricted to Repository staff only

Download (738kB) | Request a copy

Abstract

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.

Item Type: Article (Journal)
Additional Information: 6566/62522
Uncontrolled Keywords: Optimization Problem, Minimum Vertex Cover, Small Instance Graphs, Maximum Degree Algorithm, Vertex Support Algorithm, NP-Complete Problem
Subjects: T Technology > T Technology (General) > T10.5 Communication of technical information
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button): Kulliyyah of Information and Communication Technology > Department of Information System
Kulliyyah of Information and Communication Technology > Department of Information System
Depositing User: Asadullah Shah Syed
Date Deposited: 28 Mar 2018 11:32
Last Modified: 30 Jul 2018 16:26
URI: http://irep.iium.edu.my/id/eprint/62522

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year