Detecting robust cliques in graphs subject to uncertain edge failures Academic Article uri icon


  • © 2016, Springer Science+Business Media New York. This paper develops and compares several heuristic approaches, as well as an exact combinatorial branch-and-bound algorithm, for detecting maximum robust cliques in graphs subjected to multiple uncertain edge failures. The desired robustness properties are enforced using conditional value-at-risk measure. The proposed heuristics are adaptations of the well-known tabu search and GRASP methods, whereas the exact approach is an extension of Östergård’s algorithm for the maximum clique problem. The results of computational experiments on DIMACS graph instances are reported.

author list (cited authors)

  • Yezerska, O., Butenko, S., & Boginski, V. L.

citation count

  • 6

publication date

  • March 2016