A Method for Computing Upper Bounds on the Size of a Maximum Clique
Commun. Korean Math. Soc. 2003 Vol. 18, No. 4, 745-754 Printed December 1, 2003
Koonchan Kim Keimyung University
Abstract : 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
