SAT-based algorithm for finding all maximal cliques
Haitao Wu, Ningbo Hao, Wen Kuang Chou · International Journal of Computational Science and Engineering · 2016
Finding maximal clique of a graph is a fundamental problem in graph theory. In this paper, a fact is proved that the problem of finding all maximal cliques of a graph can be naturally expressed as relatively simple constraints of SAT model. First tolerance class and discernibility function for maximal cliques are defined and the characteristic and theorem over them are presented in detail, thus the process of finding all maximal cliques can be transformed as generating corresponding expression of SAT model. Then SAT-based algorithm is designed for finding all maximal cliques in a graph, and finally the effectiveness of this algorithm is demonstrated by using actual instance of a known undirected and connected graph.