.png){kind=icon}
返回
Minimum cost edge blocker clique problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-019-03315-x.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Given a graph with weights on its vertices and blocking costs on its edges, and a user-defined threshold tau 0 the minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cost subset of edges so that each clique's weight is bounded above by tau Clusters composed of important actors with quick communications can be effectively modeled as large-weight cliques in real-world settings such as social, communication, and biological systems. Here, we prove that EBCP is NP-hard even when tau is a fixed parameter, and propose a combinatorial lower bound for its optimal objective. A class of inequalities that are valid for the set of feasible solution to EBCP is identified, and sufficient conditions for these inequalities to induce facets are presented. Using this class of inequalities, EBCP is formulated as a linear 0-1 program including potentially exponential number of constraints. We develop the first problem-specific branch-and-cut algorithm to solve EBCP, which utilizes the aforementioned constraints in a lazy manner. We also developed the first combinatorial branch-and-bound solution approach for this problem, which aims to handle large graph instances. Finally, computational results of solving EBCP on a collection of random graphs and power-law real-world networks by using our proposed exact algorithms are also provided.
Keyword:
Edge blocker
Maximum weighted clique
NP-hard
Exact algorithms
Network interdiction
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.5
论文数:
8.1K
被引数:
2.1W
机构
引用论文
In vitro reconstruction of a tissue-engineered endothelialized bladder from a single porcine biopsy从单个猪活检中体外重建组织工程化的内皮化膀胱
.png){kind=icon}
PREAI
分享收藏
Biological Aspect of Indian Scad (Decapterus russelli) Caught by Purse Seine in North Coast of Sumenep Waters, East Java印度鲹（Decapterus russelli）在东爪哇苏门北海岸水域 purse seine 捕捞的生物特性研究
OAAI
OAAI分享收藏First Report of Zoonotic Genotype of Giardia duodenalis in Mussels (Mytilus edulis) from Patagonia Argentina来自阿根廷巴塔哥尼亚的贻贝 (Mytilus edulis) 中 十二指肠贾第鞭毛虫 的人畜共患病基因型的第一份报告OAAI
OAAI分享收藏
查看更多内容