Most Valuable Player Algorithm for Solving Minimum Vertex Cover Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 8
Abstract
Minimum Vertex Cover Problem (MVCP) is a combinatorial optimization problem that is utilized to formulate multiple real-life applications. Owing to this fact, abundant research has been undertaken to discover valuable MVCP solutions. Most Valuable Player Algorithm (MVPA) is a recently developed metaheuristic algorithm that inspires its idea from team-based sports. In this paper, the MVPA_MVCP algorithm is introduced as an adaptation of the MVPA for the MVCP. The MVPA_MVCP algorithm is implemented using Java programming language and tested on a Microsoft Azure virtual machine. The performance of the MVPA_MVCP algorithm is evaluated analytically in terms of run time complexity. Its average-case run time complexity is ceased to Θ(I(|V|+|E|)), where I is the size of the initial population, |V| is the number of vertices and |E| is the number of edges of the tested graph. The MVPA_MVCP algorithm is evaluated experimentally in terms of the quality of gained solutions and the run time. The experimental results over 15 instances of DIMACS benchmark revealed that the MVPA_MVCP algorithm could, in the best case, get the best known optimal solution for seven data instances. Also, the experimental findings exposed that there is a direct relation between the number of edges of the graph under test and the run time.
Authors and Affiliations
Hebatullah Khattab, Ahmad Sharieh, Basel A. Mahafzah
Keywords
Related Articles
- EP ID EP626597
- DOI 10.14569/IJACSA.2019.0100821
- Views 107
- Downloads 0
Intrusion Detection System with Correlation Engine and Vulnerability Assessment
The proposed Intrusion Detection System (IDS) which is implemented with modern technologies to address certain prevailing problems in existing intrusion detection systems’ is capable of giving an advanced output to the s...
An Online Character Recognition System to Convert Grantha Script to Malayalam
This paper presents a novel approach to recognize Grantha, an ancient script in South India and converting it to Malayalam, a prevalent language in South India using online character recognition mechanism. The moti...
Research on Islanding Detection of Grid-Connected System
This paper proposed a modified detection based on the point of common coupling (PCC) voltage in the three-phrase inverter, combined over/under frequency protection, to achieve the detection of islanding states rapidly. I...
Analyzing the Diverse Impacts of Conventional Distributed Energy Resources on Distribution System
In recent years, the rapid boost in energy demand around the globe has put power system in stress. To fulfill the energy demands and confine technical losses, researchers are eager to investigate the diverse impacts of D...
Using Real-World Car Traffic Dataset in Vehicular Ad Hoc Network Performance Evaluation
Vehicular ad hoc networking is an emerging paradigm which is gaining much interest with the development of new topics such as the connected vehicle, the autonomous vehicle, and also new high-speed mobile communication te...