In a graph G, a k-club is a vertex set inducing a subgraph of diameter k. These structures play an important role in several applications arising in social and behavioral sciences. We derive some properties of k-clubs and we propose three heuristics for determining a largest k-club in a graph. Comparative computational results confirm the speed and efficiency of these heuristics.
Paru en août 1998 , 13 pages
Ce cahier a été révisé en mars 1999