.png){kind=icon}
返回
Minimum edge blocker dominating set problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2015.05.037.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r> 0, remove a minimum number of edges so that the weight of any dominating set in the remaining graph is at least r. Dominating sets are used in a wide variety of graph-based applications such as the analysis of wireless and social networks. We show that the decision version of EBDP is NP-hard for any fixed r> 0. We present an analytical lower bound for the value of an optimal solution to EBDP and formulate this problem as a linear 0-1 program with a large number of constraints. We also study the convex hull of feasible solutions to EBDP and identify facet-inducing inequalities for this polytope. Furthermore, we develop the first exact algorithm for solving EBDP, which solves the proposed formulation by a branch-and-cut approach where nontrivial constraints are applied in a lazy fashion. Finally, we also provide the computational results obtained by using our approach on a test-bed of randomly generated instances and real-life power-law graphs. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
Keyword:
Network interdiction
Minimum weighted dominating set
NP-hardness
Branch-and-cut algorithm
Critical elements detection
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
First Report of Zoonotic Genotype of Giardia duodenalis in Mussels (Mytilus edulis) from Patagonia Argentina来自阿根廷巴塔哥尼亚的贻贝 (Mytilus edulis) 中 十二指肠贾第鞭毛虫 的人畜共患病基因型的第一份报告OAAI
OAAI分享收藏A multi-task neural network for multilingual sentiment classification and language detection on Twitter用于Twitter多语言情感分类和语言检测的多任务神经网络
PREAI
分享收藏
查看更多内容