Communications of the
Korean Mathematical Society CKMS

Maximum clique problem is to find a maximum clique (largest in size) in an undirected graph $G$. We present a method that computes either a maximum clique or an upper bound for the size of a maximum clique in $G$. We show that this method performs well on certain class of graphs and discuss the application of this method in a branch and bound algorithm for solving maximum clique problem, whose efficiency is depended on the computation of good upper bounds.

Keywords: maximum clique problem, upper bound, branch and bound algorithm, clique, graph

MSC numbers: 05C69