WSEAS Transactions on Systems and Control
Print ISSN: 1991-8763, E-ISSN: 2224-2856
Volume 15, 2020
Testing a Heuristic Algorithm for Finding a Maximum Clique on DIMACS and Facebook Graphs
Authors: , , , , ,
Abstract: In this paper we propose a new heuristic algorithm for solving a maximum clique search problem (MCP). While the proposed algorithm (called TrustCLQ) uses a general approach to solving MCP, it is almost independent of the order of vertices and does not exploit a partition of the graph into independent sets. The algorithm was tested on DIMACS library graphs which are often employed for testing MCP solution algorithms. TrustCLQ algorithm was compared with the well-known ILS heuristic algorithm (as well as with a standard algorithm from networkx library) on DIMACS data sets. Moreover, TrustCLQ algorithm has been tested on Facebook social graphs
Search Articles
Keywords: Heuristic algorithm, Graphs, Cliques, Network analysis, Maximum clique problem, DIMACS graphs, Social graphs
Pages: 93-101
DOI: 10.37394/23203.2020.15.11