Premium
The strongly connected reliability of complete digraphs
Author(s) -
Brown J.I.,
Li Xiaohu
Publication year - 2005
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.20060
Subject(s) - digraph , vertex connectivity , vertex (graph theory) , strongly connected component , combinatorics , fist , mathematics , reliability (semiconductor) , connected component , connectivity , discrete mathematics , computer science , graph , physiology , power (physics) , physics , quantum mechanics , biology
Given a digraph D , consider the model where each vertex is always operational, but the edges are independently operational with probability p . The strongly connected reliability of D , scRel( D , p ), is the probability that the spanning subgraph of D consisting of the operational edges is strongly connected. One can view strongly connected reliability as the probability that any vertex can send information to any other vertex, given that edges fail independently. There are very few classes for which there is an efficient algorithm for calculating the strongly connected reliability. This article presents the fist polynomial time algorithm for computing the strongly connected reliability of complete digraphs, that is, digraphs in which every vertex is joined to every other vertex by exactly one edge (one in each direction). © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 165–168 2005