Authors: Haitao Wu; Ningbo Hao; Wen-Kuang Chou
Addresses: Software School, Huanghuai University, Zhumadian, Henan 463000, China ' Software School, Huanghuai University, Zhumadian, Henan 463000, China ' Department of Computer Science and Information Management, Providence University, Taichung, 43301, Taiwan
Abstract: 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.
Keywords: graph theory; SAT problem; satisfiability problem; maximal cliques; undirected graph; DIMACS benchmark.
International Journal of Computational Science and Engineering, 2016 Vol.12 No.2/3, pp.186 - 191
Received: 21 Sep 2015
Accepted: 05 Nov 2015
Published online: 28 Apr 2016 *