EconPapers    
Economics at your fingertips  
 

On Fault-Tolerant Low-Diameter Clusters in Graphs

Yajun Lu (ylu@jsu.edu), Hosseinali Salemi (hsalemi@iastate.edu), Balabhaskar Balasundaram (baski@okstate.edu) and Austin Buchanan (buchanan@okstate.edu)
Additional contact information
Yajun Lu: Department of Management & Marketing, Jacksonville State University, Jacksonville, Alabama 36265
Hosseinali Salemi: Department of Industrial & Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011
Balabhaskar Balasundaram: School of Industrial Engineering & Management, Oklahoma State University, Stillwater, Oklahoma 74078
Austin Buchanan: School of Industrial Engineering & Management, Oklahoma State University, Stillwater, Oklahoma 74078

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3181-3199

Abstract: Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the s -club, which is a vertex subset that induces a subgraph of diameter at most s . This model has found use in a variety of fields because low-diameter clusters have practical significance in many applications. As this property is not hereditary on vertex-induced subgraphs, the diameter of a subgraph could increase upon the removal of some vertices and the subgraph could even become disconnected. For example, star graphs have diameter two but can be disconnected by removing the central vertex. The pursuit of a fault-tolerant extension of the s -club model has spawned two variants that we study in this article: robust s -clubs and hereditary s -clubs. We analyze the complexity of the verification and optimization problems associated with these variants. Then, we propose cut-like integer programming formulations for both variants whenever possible and investigate the separation complexity of the cut-like constraints. We demonstrate through our extensive computational experiments that the algorithmic ideas we introduce enable us to solve the problems to optimality on benchmark instances with several thousand vertices. This work lays the foundations for effective mathematical programming approaches for finding fault-tolerant s -clubs in large-scale networks.

Keywords: integer programming; hereditary s -clubs; robust s -clubs; branch-and-cut; social network analysis (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1231 (application/pdf)

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:inm:orijoc:v:34:y:2022:i:6:p:3181-3199

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher (casher@informs.org).

 
Page updated 2024-12-28
Handle: RePEc:inm:orijoc:v:34:y:2022:i:6:p:3181-3199