.png){kind=icon}
返回
On Zero Forcing Sets and Network Controllability—Computation and Edge Augmentation
.png){kind=icon}
PRE
AI
DOI：10.1109/TCNS.2023.3285872.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This article studies the problem of computing a minimum zero forcing set (ZFS) in undirected graphs and presents new approaches to reducing the size of the minimum ZFS via edge augmentation. The minimum ZFS problem has numerous applications; for instance, it relates to the minimum leader selection problem for the strong structural controllability of networks defined over graphs. Computing a minimum ZFS is an NP-hard problem in general. We show that the greedy heuristic for the ZFS computation, though it typically performs well, could give arbitrarily bad solutions for some graphs. We provide a linear-time algorithm to compute a minimum ZFS in trees and a complete characterization of the minimum ZFS in the clique chain graphs. We also present a game-theoretic solution for general graphs by formalizing the minimum ZFS problem as a potential game. In addition, we consider the effect of edge augmentation on the size of the ZFS. Adding edges could improve network robustness; however, it could increase the size of the ZFS. We show that adding a set of carefully selected missing edges to a graph may actually reduce the size of the minimum ZFS. Finally, we numerically evaluate our results on random graphs.
Keyword:
Controllability
Color
Heuristic algorithms
Network systems
Games
Process control
Computer science
Dynamics over graphs
edge augmentation
strong structural controllability
zero forcing sets (ZFSs)
期刊
IF:
5
论文数:
1.6K
被引数:
5.8K
机构
引用论文
.png){kind=icon}
Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks网络上演化的系统的零强迫，线性和量子可控性
OAAI
OAAI分享收藏
查看更多内容