On biconnected and fragile subgraphs of low diameter

Oleksandra Yezerska, Foad Mahdavi Pajouh, Sergiy Butenko

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)390-400
Number of pages11
JournalEuropean Journal of Operational Research
Volume263
Issue number2
DOIs
StatePublished - 1 Dec 2017

Keywords

  • 2-clubs
  • Biconnected 2-clubs
  • Branch-and-cut
  • Combinatorial branch-and-bound
  • Fragile 2-clubs
  • Robust network clusters

Fingerprint

Dive into the research topics of 'On biconnected and fragile subgraphs of low diameter'. Together they form a unique fingerprint.

Cite this