Detecting robust cliques in graphs subject to uncertain edge failures

Oleksandra Yezerska (), Sergiy Butenko () and Vladimir L. Boginski ()
Additional contact information
Oleksandra Yezerska: Texas A&M University
Sergiy Butenko: Texas A&M University
Vladimir L. Boginski: University of Florida

Annals of Operations Research, 2018, vol. 262, issue 1, No 7, 109-132

Abstract: 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.

Keywords: Maximum clique; Robust clique; Conditional value-at-risk; Heuristic; Tabu search; GRASP (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2161-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:262:y:2018:i:1:d:10.1007_s10479-016-2161-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-016-2161-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().