Heuristics for finding k-clubs in an undirected graph

Authors
Bourjolly, JM Laporte, G Pesant, G
Citation
Jm. Bourjolly et al., Heuristics for finding k-clubs in an undirected graph, COMPUT OPER, 27(6), 2000, pp. 559-569
Citations number
26
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
27
Issue
6
Year of publication
2000
Pages
559 - 569
Database
ISI
SICI code
0305-0548(200005)27:6<559:HFFKIA>2.0.ZU;2-P
Abstract
In a graph G, a k-club is a vertex set inducing a subgraph of diameter k. T hese structures play an important role in several applications arising in s ocial and behavioral sciences. We derive some properties of k-clubs and we propose three heuristics for determining a largest k-club in a graph. Compa rative computational results confirm the speed and efficiency of these heur istics.