期刊
ANNALS OF OPERATIONS RESEARCH
卷 276, 期 1-2, 页码 267-291出版社
SPRINGER
DOI: 10.1007/s10479-017-2665-2
关键词
s-Clubs; Partitioning; Graph-based clustering; Integer programming; Combinatorial branch-and-bound
资金
- AFRL Mathematical Modeling and Optimization Institute
- AFOSR [FA8651-14-2-0005]
- NSF [CMMI-1538493]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据