TY - JOUR
ID - 25385
TI - A local core number based algorithm for the maximum clique problem
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Mohammadi, Neda
AU - Kadivar, Mehdi
AD - Department of computer science, University of Shahrekord, Shahrekord, Iran
Y1 - 2021
PY - 2021
VL - 10
IS - 3
SP - 149
EP - 163
KW - Branch and bound
KW - Core number
KW - Maximum clique
DO - 10.22108/toc.2021.120153.1686
N2 - The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph. MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications. In this paper, we present two branch-and-bound exact algorithms for finding a maximum clique in an undirected graph. Many efficient exact branch and bound maximum clique algorithms use approximate coloring to compute an upper bound on the clique number but, as a new pruning strategy, we show that local core number is more efficient. Moreover, instead of neighbors set of a vertex, our search area is restricted to a subset of the set in each subproblem which speeds up clique finding process. This subset is based on the core of the vertices of a given graph. We improved the MCQ and MaxCliqueDyn algorithms with respect to the new pruning strategy and search area restriction. Experimental results demonstrate that the improved algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs.
UR - https://toc.ui.ac.ir/article_25385.html
L1 - https://toc.ui.ac.ir/article_25385_50a91fd9b6c1a6f01801fd7000d2ca60.pdf
ER -