An effective branch-and-bound algorithm for the maximum s-bundle problem

Yi Zhou, Weibo Lin, Jin-Kao Hao, Mingyu Xiao and Yan Jin

European Journal of Operational Research, 2022, vol. 297, issue 1, 27-39

Abstract: An s-bundle (where s is a positive integer) is a connected graph, the vertex connectivity of which is at least n−s, where n is the number of vertices in the graph. As a relaxation of the classical clique model, the s-bundle is relevant for representing cohesive groups with an emphasis on the connectivity of members; thus, it is of great practical importance. In this work, we investigate the fundamental problem of finding the maximum s-bundle from a given graph and present an effective branch-and-bound algorithm for solving this NP-hard problem. The proposed algorithm is distinguished owing to its new multi-branching rules, graph coloring-based bounding technique, and reduction rules using structural information. The experiments indicate that the algorithm outperforms the best-known approaches on a wide range of well-known benchmark graphs for different s values. In particular, compared with the popular Russian Doll Search algorithm, the proposed algorithm almost doubles the success rate of solving large social networks in an hour when s=5.

Keywords: Branch and bound; Combinatorial optimization; Graph theory; Clique relaxation; s-Bundle (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721003957
Full text for ScienceDirect subscribers only

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:eee:ejores:v:297:y:2022:i:1:p:27-39

DOI: 10.1016/j.ejor.2021.05.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().