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

abstract

• 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 stergrds algorithm for the maximum clique problem. The results of computational experiments on DIMACS graph instances are reported.

authors

• Butenko, Sergiy

published proceedings

• Annals of Operations Research

author list (cited authors)

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

citation count

• 8

complete list of authors

• Yezerska, Oleksandra||Butenko, Sergiy||Boginski, Vladimir L

publication date

• March 2018

publisher

• Springer Nature  Publisher

published in

• Annals of Operations Research  Journal

keywords

• 49 Mathematical Sciences
• 4901 Applied Mathematics
• 4904 Pure Mathematics

Digital Object Identifier (DOI)

• 10.1007/s10479-016-2161-0

start page

• 109

end page

• 132

volume

• 262

issue

• 1

URL

• http://dx.doi.org/10.1007/s10479-016-2161-0