期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 263, 期 2, 页码 390-400出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2017.05.020
关键词
2-clubs; Biconnected 2-clubs; Fragile 2-clubs; Combinatorial branch-and-bound; Branch-and-cut; Robust network clusters
资金
- AFRL Mathematical Modeling and Optimization Institute
- NSF [CMMI-1538493]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1538493] Funding Source: National Science Foundation
An s-club is a subset of vertices inducing a subgraph with a diameter of at most s. It is commonly used to characterize network clusters in applications for which easy reachability between group members is of high importance. In this paper, we study two special cases of the 2-club model - a biconnected 2-club, and a fragile (not biconnected) 2-club, respectively. We investigate certain properties of both models, propose a combinatorial branch-and-bound algorithm to find a maximum biconnected 2-club, and design a polynomial-time algorithm for finding a maximum fragile 2-club in a given graph. In addition, we formulate the maximum biconnected 2-club problem as a linear 0-1 program and solve this formulation by a branch-and-cut approach where some nontrivial constraints are applied in a lazy fashion. Finally, numerical results obtained using the proposed algorithms on a test-bed of randomly generated instances and real-life graphs are also provided. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据