TY - GEN

T1 - Decomposition into Biconnected Components for Calculation of Diameter Constrained Network Reliability

AU - Ryabinin, Daniil

AU - Migov, Denis

N1 - Conference code: 21

PY - 2025/11/5

Y1 - 2025/11/5

N2 - The reliability of a network with a diameter constraint is defined as the probability that terminal nodes remain connected by paths of limited length. This metric is crucial for quality-of-service guarantees in modern communication systems where latency is a key factor. As the problem of calculating diameter constrained reliability is NP-hard, efficient reduction and decomposition methods are essential for reliability analysis of even medium-scale networks. The paper introduces a novel decomposition approach for 2-terminal networks that can be represented as a chain of biconnected components. We present a generalized formula that extends previous results on decomposition via a cutnode to an arbitrary number of cutnodes and biconnected components. This method avoids the recursive overhead and repetitive computation of the previous approach, leading to a significant reduction in computation time for networks of appropriate topology. Experimental results demonstrate that the method proposed provides speedup of several orders of magnitude, enabling the exact reliability analysis of larger and more complex networks.

AB - The reliability of a network with a diameter constraint is defined as the probability that terminal nodes remain connected by paths of limited length. This metric is crucial for quality-of-service guarantees in modern communication systems where latency is a key factor. As the problem of calculating diameter constrained reliability is NP-hard, efficient reduction and decomposition methods are essential for reliability analysis of even medium-scale networks. The paper introduces a novel decomposition approach for 2-terminal networks that can be represented as a chain of biconnected components. We present a generalized formula that extends previous results on decomposition via a cutnode to an arbitrary number of cutnodes and biconnected components. This method avoids the recursive overhead and repetitive computation of the previous approach, leading to a significant reduction in computation time for networks of appropriate topology. Experimental results demonstrate that the method proposed provides speedup of several orders of magnitude, enabling the exact reliability analysis of larger and more complex networks.

UR - https://www.scopus.com/pages/publications/105023665313

UR - https://www.mendeley.com/catalogue/982748e0-ec87-3e2b-92d4-9fa85df98c0c/

U2 - 10.1109/opcs67346.2025.11219379

DO - 10.1109/opcs67346.2025.11219379

M3 - Conference contribution

SN - 979-8-3315-8982-0

SP - 1

EP - 4

BT - Proceedings - 2025 21st International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS)

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 21st International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS)

Y2 - 7 July 2025 through 17 July 2025

ER -