Title :
A unified domination approach for reliability analysis of networks with arbitrary logic in vertices
Author :
Chernyak, Arkadi A. ; Chernyak, Zhanna A.
Author_Institution :
State Econ. Univ., Minsk, Byelorussia
fDate :
3/1/1996 12:00:00 AM
Abstract :
The concept of a probabilistic graph G has been used as a universal model for network reliability. Most of the literature on this subject concentrates on computing various reliability measures (such as k-terminal reliability or all-terminal reliability) which are the probability that vertices of G can communicate with other specified vertices. Primarily, this paper provides a common theoretical framework for addressing k-terminal reliability problems. To this end, it extends the model admitting vertex functions of G to be arbitrary monotone Boolean functions: in this case G is called a monotone (S,t)-graph. In such graphs the signal passability across a node is carried out in accordance with collections of signals delivered on the node inputs from other ones, the collections are subjected to some logic principle realized by a Boolean function. Monotone (S,t)-graphs include all known classes of directed multi-terminal network reliability models. The main result of this paper is the reliability expression for computing the probability of an acyclic monotone (S,t)-graph G being operational. The expression uses the local domination parameters introduced here. That reduces the system level of consideration to the element level, providing a unifying understanding of the combinatorial nature of some results based on the domination theory and developed earlier for ordinary networks
Keywords :
Boolean functions; directed graphs; probability; reliability theory; acyclic monotone (S,t)-graph; all-terminal reliability; arbitrary logic; arbitrary monotone Boolean functions; directed acyclic graphs; directed multi-terminal network reliability models; k-terminal reliability; local domination parameters; monotone (S,t)-graph; probabilistic graph; reliability analysis; reliability measures; signal passability; topological formula; unified domination approach; vertex functions; Boolean functions; Informatics; Intelligent networks; Logic; Reliability theory; Telecommunication network reliability;
Journal_Title :
Reliability, IEEE Transactions on