On inclusionwise maximal and maximum cardinality -clubs in graphs
- 作者：F. Mahdavi Pajouh mahdavi@okstate.edu ; B. Balasundaram ; baski@okstate.edu
- 关键词：Clique ; k-club ; Exact combinatorial algorithms ; Graph-based data mining ; Social network analysis
- 刊名：Discrete Optimization
- 出版年：2012
- 期刊代码：4_15725286
- 类别：mt
- 出版时间：May, 2012
- 卷：9
- 期：2
- 页码：84-97
- 文件大小：630 K
摘要
A -club is a distance-based graph-theoretic generalization of a clique, originally introduced to model cohesive social subgroups in social network analysis. The -clubs represent low diameter clusters in graphs and are appropriate for various graph-based data mining applications. Unlike cliques, the -club model is nonhereditary, meaning every subset of a -club is not necessarily a -club. In this article, we settle an open problem establishing the intractability of testing inclusion-wise maximality of -clubs. This result is in contrast to polynomial-time verifiability of maximal cliques, and is a direct consequence of its nonhereditary nature. We also identify a class of graphs for which this problem is polynomial-time solvable. We propose a distance coloring based upper-bounding scheme and a bounded enumeration based lower-bounding routine and employ them in a combinatorial branch-and-bound algorithm for finding maximum cardinality -clubs. Computational results from using the proposed algorithms on 200-vertex graphs are also provided.