Approximate maximum clique algorithm (AMCA): A clever technique for solving the maximum clique problem through near optimal algorithm for minimum vertex cover problem

Fayaz, Muhammad and Arshad,, Shakeel and Shah,, Abdul Salam and Shah, Asadullah (2018) Approximate maximum clique algorithm (AMCA): A clever technique for solving the maximum clique problem through near optimal algorithm for minimum vertex cover problem. International Journal of control and Automation, 11 (3). pp. 35-44. ISSN 2005-4297

	PDF (SCOPUS) - Supplemental Material Restricted to Registered users only Download (503kB) | Request a copy
	PDF - Published Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Background and Objective: The process of solving the Maximum Clique (MC) problem through approximation algorithms is harder, however, the Maximum Vertex Cover (MVC) problem can easily be solved using approximation algorithms. In this paper, a technique has been proposed to use the approximation algorithms of Minimum Vertex Cover (MVC) for the solution of the Maximum Cliques (MC) problem. Material and methods: To test the proposed technique, selected approximation algorithms have been developed to small graph instances. The algorithms that were used for experiments are Maximum Degree Greedy (MDG). Vertex support Algorithm (VSA). Mean of Neighbors of Minimum Degree Algorithm (MNMA), Modified Vertex Support Algorithm (MVSA), Maximum Adjacent Minimum Degree Algorithm (MAMA), and Clever Steady Strategy Algorithms (CSSA). Results: The development of an efficient approximation algorithm for the Maximum Clique (MC) problem is very difficult due to its complex nature. The only way left is to use the approximation algorithm of Minimum Vertex Cover (MVC) for the solution of the Maximum Clique (MC) problem. The experimental analysis of the proposed algorithm has revealed that the Maximum Clique (MC) problem can be efficiently solved with approximation algorithms of Minimum Vertex Cover (MVC). The proposed algorithm has efficiently solved the MC problem within the reduced time limit. conclusions: It is a difficult task to directly solve the MC problem through approximation algorithms. The proposed method provides a platform to efficiently solve the MC problem by using approximation algorithm of Minimum Vertex Cover (MVC).

Item Type:	Article (Journal)
Additional Information:	6566/63287
Uncontrolled Keywords:	Graph Instances, Minimum Vertex Cover, Maximum Independent Set (MIS), Maximum Clique Problem, NP-Complete Problem
Subjects:	T Technology > T Technology (General) T Technology > T Technology (General) > T10.5 Communication of technical information
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology > Department of Information System Kulliyyah of Information and Communication Technology > Department of Information System Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Prof Asadullah Shah
Date Deposited:	17 Apr 2018 08:43
Last Modified:	31 Jul 2018 09:26
URI:	http://irep.iium.edu.my/id/eprint/63287

Actions (login required)

View Item