On robust clusters of minimum cardinality in networks Academic Article uri icon


  • © 2015, Springer Science+Business Media New York. This paper studies two clique relaxation models, k-blocks and k-robust 2-clubs, used to describe structurally cohesive clusters with good robustness and reachability properties. The minimization version of the two problems are shown to be hard to approximate for k≥ 3 and k≥ 4 , respectively. Integer programming formulations are proposed and a polyhedral study is presented. The results of sample numerical experiments on several graph instances are also reported.

author list (cited authors)

  • Balasubramaniam, C., & Butenko, S.

citation count

  • 4

publication date

  • February 2017