A New Exact Algorithm for the Maximum Weight Clique Problem
Kazuaki Yamaguchi, Sumio Masuda · ITC-CSCC :International Technical Conference on Circuits Systems, Computers and Communications · 2008
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.