.png){kind=icon}
返回
An effective branch-and-bound algorithm for the maximum s -bundle problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2021.05.001.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 . (c) 2021 Elsevier B.V. All rights reserved.
Keyword:
Branch and bound
Combinatorial optimization
Graph theory
Clique relaxation
s-Bundle
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。