On robust clusters of minimum cardinality in networks

详细信息    查看全文

• 作者：Chitra Balasubramaniam ; Sergiy Butenko
• 关键词：Clique relaxations ; Connectivity ; k ; Block ; k ; Robust s ; club ; Structural cohesion
• 刊名：Annals of Operations Research
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：249
• 期：1-2
• 页码：17-37
• 全文大小：
• 刊物类别：Business and Economics
• 刊物主题：Operation Research/Decision Theory; Combinatorics; Theory of Computation;
• 出版者：Springer US
• ISSN：1572-9338
• 卷排序：249

文摘

This paper studies two clique relaxation models, k-blocks and k-robust 2-clubs, used to describe structurally cohesive clusters with good robustness and reachability properties. The minimization version of the two problems are shown to be hard to approximate for \(k \ge 3\) and \(k \ge 4\), respectively. Integer programming formulations are proposed and a polyhedral study is presented. The results of sample numerical experiments on several graph instances are also reported.