Premium
Network reliability analysis using 2‐connected digraph reductions
Author(s) -
Agrawal Avinash,
Satyanarayana A.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150209
Subject(s) - digraph , combinatorics , reduction (mathematics) , mathematics , strongly connected component , discrete mathematics , directed graph , class (philosophy) , computer science , geometry , artificial intelligence
The problem of computing the SKT reliability, the probability that a source s can send communication to a specified set of terminals K ⊂ V in a probabilistic digraph D = (V,E) is considered. For general digraphs, this problem is known to be NP‐hard and it is helpful to consider schemes that can decompose the problem into a number of smaller problems. A non‐separable digraph is 2‐connected if it contains a separation pair, a pair of nodes whose removal disconnects the digraph. Such a digraph can be partitioned into two or more segments. It is shown that at least one of these segments can be replaced by a simpler structure; this replacement results in an exact reliability preserving reduction. The proposed reduction scheme is general and is applicable to all digraphs containing a separation pair; earlier methods could only handle special cases. For a class of digraphs, called BSP digraphs, such a reduction is always admissible and the SKT reliability can be computed in time O(∣ E ∣). A digraph is a BSP digraph if its underlying undirected graph is series‐parallel. A BSP digraph can be cyclic or acyclic. No polynomial‐time algorithms were previously known for this class of digraphs.