Heuristics for Finding k-Clubs in an Undirected Graph

, et

référence BibTeX

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

Axe de recherche

Application de recherche