Summary
International Technical Conference on Circuits/Systems, Computers and Communications
2008
Session Number:F3
Session:
Number:F3-1
A New Exact Algorithm for the Maximum Weight Clique Problem
Kazuaki Yamaguchi, Sumio Masuda,
pp.-
Publication Date:2008/7/7
Online ISSN:2188-5079
Summary:
Given an undirected graph with weight for each vertex, the maximum weight clique problem is to find the clique of the maximum weight. Ostergard proposed a fast exact algorithm for solving this problem. We show his algorithm is not efficient for very dense graphs. We propose an exact algorithm for the problem, which is faster than Ostergard's algorithm in case the graph is dense. We show the efficiency of our algorithm with some experimental results.