Title: SAT-based algorithm for finding all maximal cliques

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.

DOI: 10.1504/IJCSE.2016.076286

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: 30 Apr 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article