Exact algorithms for the minimum s-club partitioning problem

Oleksandra Yezerska, Foad Mahdavi Pajouh, Alexander Veremyev, Sergiy Butenko

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)267-291
Number of pages25
JournalAnnals of Operations Research
Volume276
Issue number1-2
DOIs
StatePublished - 1 May 2019

Keywords

  • Combinatorial branch-and-bound
  • Graph-based clustering
  • Integer programming
  • Partitioning
  • s-Clubs

Fingerprint

Dive into the research topics of 'Exact algorithms for the minimum s-club partitioning problem'. Together they form a unique fingerprint.

Cite this