Premium
A recursive algorithm for directed‐graph reliability
Author(s) -
Buzacott J. A.
Publication year - 1983
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.3230130208
Subject(s) - directed graph , undirected graph , computer science , reliability (semiconductor) , algorithm , graph , directed acyclic graph , mathematics , theoretical computer science , power (physics) , physics , quantum mechanics
It is shown that the recursive algorithm for determining the reliability measures relating to the connection of nodes in an undirected graph can also be applied to directed graphs with no increase in the computational requirements. The resulting algorithm is compared with a number of other directed‐graph reliability algorithms and is shown to require, on complete graphs, significantly fewer multiplications than any existing algorithm.