Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 263, Issue 2, Pages 390-400Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2017.05.020
Keywords
2-clubs; Biconnected 2-clubs; Fragile 2-clubs; Combinatorial branch-and-bound; Branch-and-cut; Robust network clusters
Funding
- AFRL Mathematical Modeling and Optimization Institute
- NSF [CMMI-1538493]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1538493] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available