Heuristic Algorithm for Extracting a Subset of Maximal Cliques Inside Graphs - Trinh, Anh Phuc; Dinh, Viet Sang (Old Journal, 2017)
We investigate the problem of extracting a subset of maximal cliques inside an undirected graph. This problem is considered as a NP-complete problem. In this work, we propose a heuristic algorithm that treats the above problem. In our algorithm, undirected graph is represented using the adjacency-list. Next, this representation is transformed into a new form so-called transaction database that is very familiar in data mining domain. Based on the new representation, we are able to count the frequency of subset of vertices inside undirected graph which is used to extract a set of maximal candidates that become possibly maximal cliques. Our experimental results show that this algorithm maintains a reasonable threshold in order to control its complexity.