Detecting Robust Cliques In Graphs Subject To Uncertain Edge Failures

Keywords

Conditional value-at-risk; GRASP; Heuristic; Maximum clique; Robust clique; Tabu search

Abstract

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.

Publication Date

3-1-2018

Publication Title

Annals of Operations Research

Volume

262

Issue

1

Number of Pages

109-132

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s10479-016-2161-0

Socpus ID

84961209497 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84961209497

This document is currently not available here.

Share

COinS