.png){kind=icon}
返回
Graph fragmentation problem: analysis and synthesis
.png){kind=icon}
PRE
AI
DOI：10.1111/itor.12562.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of individuals for protection, and a nonprotected target node immediately destroys all reachable nodes. The goal is to minimize the expected number of destroyed nodes in the network. In this paper, we address the GFP by several approaches: metaheuristics, approximation algorithms, polytime methods for specific instances, and exact methods for small instances. The computational complexity of the GFP is included in our analysis, where we formally prove that the corresponding decision version of the problem is NP-complete. Furthermore, a strong inapproximability result holds: there is no polynomial approximation algorithm with factor lower than 5/3, unless P=NP. This promotes the study of specific instances of the problem for tractability and/or exact methods in exponential time. As a synthesis, we propose new vulnerability/connectivity metrics and an interplay with game theory using a closely related combinatorial problem called component order connectivity.
Keyword:
vulnerability metrics
graph fragmentation problem
computational complexity
approximation algorithms
metaheuristics
game theory
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.9
论文数:
1.8K
被引数:
3.7K
机构
引用论文
.png){kind=icon}
Copper-promoted/catalyzed CN and CO bond cross-coupling with vinylboronic acid and its utilities
PREAI
分享收藏
查看更多内容