Exact algorithms for the minimum s-club partitioning problem

Oleksandra Yezerska (), Foad Mahdavi Pajouh (), Alexander Veremyev () and Sergiy Butenko ()
Additional contact information
Oleksandra Yezerska: Texas A&M University
Foad Mahdavi Pajouh: University of Massachusetts Boston
Alexander Veremyev: University of Central Florida
Sergiy Butenko: Texas A&M University

Annals of Operations Research, 2019, vol. 276, issue 1, No 13, 267-291

Abstract: 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$$ s = 2 and $$s=3$$ s = 3 on a test-bed of randomly generated instances and real-life graphs.

Keywords: s-Clubs; Partitioning; Graph-based clustering; Integer programming; Combinatorial branch-and-bound (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2665-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:276:y:2019:i:1:d:10.1007_s10479-017-2665-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2665-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().