TY - JOUR
T1 - On biconnected and fragile subgraphs of low diameter
AU - Yezerska, Oleksandra
AU - Mahdavi Pajouh, Foad
AU - Butenko, Sergiy
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2017/12/1
Y1 - 2017/12/1
N2 - 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.
AB - 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.
KW - 2-clubs
KW - Biconnected 2-clubs
KW - Branch-and-cut
KW - Combinatorial branch-and-bound
KW - Fragile 2-clubs
KW - Robust network clusters
UR - http://www.scopus.com/inward/record.url?scp=85020164311&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020164311&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2017.05.020
DO - 10.1016/j.ejor.2017.05.020
M3 - Article
AN - SCOPUS:85020164311
SN - 0377-2217
VL - 263
SP - 390
EP - 400
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -