In this paper, we prove that the maximum k-club problem defined on an undirected graph is NP-hard. We also give an integer programming formulation for this problem as well as an exact branch-and-bound algorithm and computational results on instances involving up to 200 vertices. Instances defined on very dense graphs can be solved to optimality within insignificant computing times. The most difficult cases appear to be those where the graph density is around 0.15.
Paru en novembre 1999 , 13 pages