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...

Full description

Bibliographic Details
Main Authors:	Fayaz, Muhammad, Arshad, S, Shah, A.S, Shah, Asadullah
Format:	Article
Language:	English
Published:	Faculty of Natural Sciences, University of Sindh 2016
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://irep.iium.edu.my/53852/ http://irep.iium.edu.my/53852/ 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

id	iium-53852
recordtype	eprints
spelling	iium-538522017-01-04T09:19:00Z http://irep.iium.edu.my/53852/ Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems Fayaz, Muhammad Arshad, S Shah, A.S Shah, Asadullah QA75 Electronic computers. Computer science 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). Faculty of Natural Sciences, University of Sindh 2016 Article PeerReviewed application/pdf en 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 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 http://sujo.usindh.edu.pk/index.php/SURJ/article/view/2722/0
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science Fayaz, Muhammad Arshad, S Shah, A.S Shah, Asadullah Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
description	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).
format	Article
author	Fayaz, Muhammad Arshad, S Shah, A.S Shah, Asadullah
author_facet	Fayaz, Muhammad Arshad, S Shah, A.S Shah, Asadullah
author_sort	Fayaz, Muhammad
title	Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
title_short	Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
title_full	Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
title_fullStr	Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
title_full_unstemmed	Max degree around (MDA) algorithm: a smart and efficient approximate algorithm for Vertex cover and independent set problems
title_sort	max degree around (mda) algorithm: a smart and efficient approximate algorithm for vertex cover and independent set problems
publisher	Faculty of Natural Sciences, University of Sindh
publishDate	2016
url	http://irep.iium.edu.my/53852/ http://irep.iium.edu.my/53852/ 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
first_indexed	2023-09-18T21:16:10Z
last_indexed	2023-09-18T21:16:10Z
_version_	1777411577244286976

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

Similar Items