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
MSC numbers : 05C69
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society.
(Rm.1109) The first building, 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd