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
相关论文
共 50 条
  • [1] Vertex-Connectivity for Node Failure Identification in Boolean Network Tomography
    Galesi, Nicola
    Ranjbar, Fariba
    Zito, Michele
    ALGORITHMS FOR SENSOR SYSTEMS, ALGOSENSORS 2019, 2019, 11931 : 79 - 95
  • [2] Hardness of approximation for vertex-connectivity network design problems
    Kortsarz, G
    Krauthgamer, R
    Lee, JR
    SIAM JOURNAL ON COMPUTING, 2004, 33 (03) : 704 - 720
  • [3] Eulerian orientations and vertex-connectivity
    Horsch, Florian
    Szigeti, Zoltan
    DISCRETE APPLIED MATHEMATICS, 2021, 289 : 115 - 124
  • [4] Hardness of approximation for vertex-connectivity network-design problems
    Kortsarz, G
    Krauthgamer, R
    Lee, JR
    APPROXIMATION ALGORITHMS FOR COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2002, 2462 : 185 - 199
  • [5] Average Distance and Vertex-Connectivity
    Dankelmann, Peter
    Mukwembi, Simon
    Swart, Henda C.
    JOURNAL OF GRAPH THEORY, 2009, 62 (02) : 157 - 177
  • [6] Directed vertex-connectivity augmentation
    Frank A.
    Mathematical Programming, 1999, 84 (3) : 537 - 553
  • [7] Vertex-connectivity and eigenvalues of graphs
    Hong, Zhen-Mu
    Xia, Zheng-Jiang
    Lai, Hong-Jian
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 579 (72-88) : 72 - 88
  • [8] The vertex-connectivity index revisited
    Amic, D
    Beslo, D
    Lucic, B
    Nikolic, S
    Trinajstic, N
    JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1998, 38 (05): : 819 - 822
  • [9] Degree distance and vertex-connectivity
    Ali, P.
    Mukwembi, S.
    Munyira, S.
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) : 2802 - 2811
  • [10] ON THE OPTIMAL VERTEX-CONNECTIVITY AUGMENTATION
    JORDAN, T
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) : 8 - 20
12345