Group for Research in Decision Analysis

G-98-41

Heuristics for Finding k-Clubs in an Undirected Graph

, , and

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.

, 13 pages

This cahier was revised in March 1999