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 111
- Downloads 0
Regression Test-Selection Technique Using Component Model Based Modification: Code to Test Traceability
Regression testing is a safeguarding procedure to validate and verify adapted software, and guarantee that no errors have emerged. However, regression testing is very costly when testers need to re-execute all the test c...
A Secured Interoperable Data Exchange Model
Interoperability enables peer systems to communicate with each other and use the functionality of peer systems effectively. It improves ability for different systems to exchange information between cooperative systems. I...
Preference in using Agile Development with Larger Team Size
Agile software development includes a group of software development methodologies based on iterative development, where requirements and solutions evolve through collaboration between cross-functional self-organizing tea...
A ’Cognitive Driving Framework’ for Collision Avoidance in Autonomous Vehicles
The Cognitive Driving Framework is a novel method for forecasting the future states of a multi-agent system that takes into consideration both the intentions of the agents as well as their beliefs about the environment....
A Qualitative Comparison of NoSQL Data Stores
Due to the proliferation of big data with large volume, velocity, complexity, and distribution among remote servers, it became obvious that traditional relational databases are unsuitable for meeting the requirements of...