Vertex-connectivity for node failure identification in Boolean Network Tomography

被引：0

作者：

Galesi, Nicola ^{[1
]}

Ranjbar, Fariba ^{[2
]}

Zito, Michele ^{[3
]}

机构：

[1] Sapienza Univ Roma, Rome, Italy

[2] Luiss Guido Carli, Rome, Italy

[3] Univ Liverpool, Liverpool, England

来源：

INFORMATION PROCESSING LETTERS | 2024年 / 184卷

关键词：

Failure identification; Boolean Network Tomography; Vertex connectivity; Augmented grids; Combinatorial problems;

D O I：

10.1016/j.ipl.2023.106450

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the node failure identification problem in undirected graphs by means of Boolean Network Tomography. We argue that vertex-connectivity plays a central role. We prove bounds on the maximum number of simultaneous node failures that can be identified in arbitrary networks. We argue that (augmented) grids are a class of networks with large failure identifiability, and provide very tight results in this context. (c) 2023 Elsevier B.V. All rights reserved.

引用

页数：7