Nordic Journal of Computing Bibliography

Patric R. J. Östergård. A New Algorithm for the Maximum-Weight Clique Problem. Nordic Journal of Computing, 8(4):424-436, Winter 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; 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


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database