کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141812 | 957093 | 2012 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On inclusionwise maximal and maximum cardinality kk-clubs in graphs On inclusionwise maximal and maximum cardinality kk-clubs in graphs](/preview/png/1141812.png)
A kk-club is a distance-based graph-theoretic generalization of a clique, originally introduced to model cohesive social subgroups in social network analysis. The kk-clubs represent low diameter clusters in graphs and are appropriate for various graph-based data mining applications. Unlike cliques, the kk-club model is nonhereditary, meaning every subset of a kk-club is not necessarily a kk-club. In this article, we settle an open problem establishing the intractability of testing inclusion-wise maximality of kk-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 kk-clubs. Computational results from using the proposed algorithms on 200-vertex graphs are also provided.
Journal: Discrete Optimization - Volume 9, Issue 2, May 2012, Pages 84–97