Journal
ANNALS OF OPERATIONS RESEARCH
Volume 276, Issue 1-2, Pages 267-291Publisher
SPRINGER
DOI: 10.1007/s10479-017-2665-2
Keywords
s-Clubs; Partitioning; Graph-based clustering; Integer programming; Combinatorial branch-and-bound
Categories
Funding
- AFRL Mathematical Modeling and Optimization Institute
- AFOSR [FA8651-14-2-0005]
- NSF [CMMI-1538493]
Ask authors/readers for more resources
Graph clustering (partitioning) is a helpful tool in understanding complex systems and analyzing their structure and internal properties. One approach for graph clustering is based on partitioning the graph into cliques. However, clique models are too restrictive and prone to errors given imperfect data. Thus, using clique relaxations instead may provide a more reasonable and applicable partitioning of the graph. An s-club is a distance-based relaxation of a clique and is formally defined as a subset of vertices inducing a subgraph with a diameter of at most s. In this work, we study the minimum s-club partitioning problem, which is to partition the graph into a minimum number of non-overlapping s-club clusters. Integer programming techniques and combinatorial branch-and-bound framework are employed to develop exact algorithms to solve this problem. We also study and compare the computational performance of the proposed algorithms for the special cases of s=2 and s=3 on a test-bed of randomly generated instances and real-life graphs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available