Groupe d’études et de recherche en analyse des décisions


Heuristics for Finding k-Clubs in an Undirected Graph

, et

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

Ce cahier a été révisé en mars 1999