صورة الغلاف

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

وصف كامل

محفوظ في:
التفاصيل البيبلوغرافية
المؤلفون الرئيسيون: Fayaz, Muhammad, Arshad, S, Shah, A.S, Shah, Asadullah
التنسيق: مقال
اللغة:English
منشور في: Faculty of Natural Sciences, University of Sindh 2016
الموضوعات:
QA75 Electronic computers. Computer science
الوصول للمادة أونلاين: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
الوسوم: إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
id my.iium.irep.53852
record_format dspace
spelling my.iium.irep.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 REM 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
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
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/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
_version_ 1643614431074058240
score 13.251813

مواد مشابهة