An Efficient approach for the Optimization version of Maximum Weighted Clique Problem

摘要

Given a graph and a weight function defined on the vertex set of a graph, the maximum weighted clique (MWC) problem calls for finding the number of vertices with maximum total weight and also any two of vertices are pairwise adjacent. In this paper, an edge based local search algorithm, called ELS, is proposed for the MWC, a well-known combinatorial optimization problem. ELS is a two phased local search method effectively finds the near optimal solutions for the MWC. A parameter 'support' of vertices defined in the ELS greatly reduces the more number of random selections among vertices and also the number of iterations and running times. Computational results on DIMACS benchmark graphs indicate that ELS is capable of achieving state-of-the-art-performance for the maximum weighted clique with reasonable average running times.