A new algorithm for the maximum-weight clique problem
Patric R. J. Östergård · 2001
Given a graph, in the maximum clique problem one wants to find the largest number of vertices, any two of which are adjacent. In the maximum-weight clique problem, the vertices have positive, integer weights, and one wants to find a clique with maximum weight. A recent algorithm for the maximum clique problem is here used as a basis for developing an algorithm for the weighted case. Computational experiments with random graphs show that this new algorithm is faster than earlier algorithms in many cases. A set of weighted graphs obtained from the problem of constructing good constant weight error-correcting codes are proposed as test cases for maximum-weight clique algorithms