Greedy Randomized Adaptive Search Procedure for the Maximum Co-k-plex Problem

Abstract

The focus of this thesis is a degree based relaxation of independent sets in graphs called co-k-plexes and the related combinatorial optimization problem of finding a maximum cardinality co-k-plex in G. This thesis develops a metaheuristic approach for solving the maximum co-k-plex problem which is known to be NP-hard. The approach is further extended for finding a maximum weighted co-k-plex in G where vertices of G are associated with specific weights. As the maximum co-k-plex problem in G is equivalent to the maximum k-plex problem in complement graph of G, many applications of this problem can be found in clustering and data mining social networks, biological networks, internet graphs and stock market graphs among others. In this thesis, a Greedy Randomized Adaptive Search Procedure (GRASP) is developed to solve the maximum co-k-plex and maximum weighted co-k-plex problems. Computational experiments are performed to study the effectiveness of the proposed metaheuristic on benchmark instances. Finally, the performance of the developed GRASP algorithms for both versions was confirmed by comparing the running time and solution quality with results obtained by an exact algorithm.