Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems

Fayaz, Muhammad and Arshad, S and Shah, A.S and Shah, Asadullah (2016) Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems. Sindh University Research Journal (Science Series), 48 (4D). pp. 17-26. ISSN 1813-1743

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

Abstract

The minimum vertex cover (MVC) and maximum independent set (MIS) problems are to be determined in terms of a graph of the small set of vertices, which cover all the edges, and a large set of vertices, no two of which are adjacent. MVC and MIS are notable for its capability of modelling other combinatorial problems and real-world applications. The aim of this paper is twofold: first to investigate failures of the state-of- the-art algorithms for MVC problem on small graphs and second to propose a simple and efficient approximation algorithm for the minimum vertex cover problem. Mostly the state of art approximation algorithms for the MVC problem are based on greedy approaches, or inspired from MIS approaches. Hence, these approaches regularly fail to provide optimal results on specific graph instances. These problems motivated to propose Max Degres Around (MDA) approximation algorithm for the MVC problem. The proposed algorithm is simple and efficient than the other heuristic algorithms for the MVC problem. In this paper, we have introduced small benchmark instances and some state of the art algorithms (MDG, VSA, and MVSA) have been tested along with the proposed algorithm. The proposed algorithm performed well as compared to counterpart algorithms tested on graphs with up to 1000 vertices and 150,000 vertices for Minimum Vertex Cover (MVC) and Maximum Independent Set (MIS).

Item Type:	Article (Journal)
Additional Information:	6566/53852
Uncontrolled Keywords:	Approximation algorithm, approximation ratio, benchmark, minimum vertex cover (MVC), NP-complete, maximum Independent Set (MIS) Problem, Max Degree Around (MDA)
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:	04 Jan 2017 17:19
Last Modified:	04 Jan 2017 17:19
URI:	http://irep.iium.edu.my/id/eprint/53852

Actions (login required)

View Item