AbstractGiven 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; in fact, one of these leads to a new record-breaking code.
Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: branch-and-bound algorithm, clique, graph algorithm
Selected references
- E. Balas and Jue Xue. Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring. Algorithmica, 15(5):397-412, May 1996.
- Ming-Shing Yu, Lin Yu Tseng, and Shoe-Jane Chang. Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs. Information Processing Letters, 46(1):7-11, 29 April 1993.