On biconnected and fragile subgraphs of low diameter
- Additional Document Info
- View All
2017 Elsevier B.V. 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 01 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.
European Journal of Operational Research
author list (cited authors)
Yezerska, O., Pajouh, F. M., & Butenko, S.
complete list of authors
Yezerska, Oleksandra||Pajouh, Foad Mahdavi||Butenko, Sergiy