Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
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 combina...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Faculty of Natural Sciences, University of Sindh
2016
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/53852/1/Max%20Degree%20Around%20Algorithm-A%20Smart%20and%20Efficient%20Approximate%20Algorithm%20for%20Vertex%20Cover%20and%20Independent%20Set%20Problems.pdf http://irep.iium.edu.my/53852/ http://sujo.usindh.edu.pk/index.php/SURJ/article/view/2722/0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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). |
|---|