On biconnected and fragile subgraphs of low diameter Academic Article uri icon

abstract

  • 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.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Yezerska, O., Pajouh, F. M., & Butenko, S.

citation count

  • 8

complete list of authors

  • Yezerska, Oleksandra||Pajouh, Foad Mahdavi||Butenko, Sergiy

publication date

  • January 2017