- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnline Submission ㆍMy Manuscript - For Reviewers - For Editors
 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