An exact algorithm for the maximum k-club problem in an undirected graph

An exact algorithm for the maximum k-club problem in an undirected graph

0.00 Avg rating0 Votes
Article ID: iaor20023403
Country: Netherlands
Volume: 138
Issue: 1
Start Page Number: 21
End Page Number: 28
Publication Date: Apr 2002
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: branch and bound, programming: integer, networks
Abstract:

In this paper, we prove that the maximum k-club problem (MkCP) 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. When k=2, the most difficult cases appear to be those where the graph density is around 0.15.

Reviews

Required fields are marked *. Your email address will not be published.