DocumentCode :
1349871
Title :
Using the Decomposition-Tree of a Network in Reliability Computation
Author :
Hagstrom, Jane N.
Author_Institution :
Department of Quantitative Methods; University of Illinois; Box 4348; Chicago, Illinois 60680 USA.
Issue :
1
fYear :
1983
fDate :
4/1/1983 12:00:00 AM
Firstpage :
71
Lastpage :
78
Abstract :
Available algorithms for measures of network reliability require computation time f(n) where f is at least exponential in n, the number of failure-prone elements in the system. Modularization is a familiar method of decomposing a network reliability problem into a set of subproblems. This decomposition reduces required computation time from f(n) to a sum of f(ni), ni < n, usually a considerable saving. For a 2-terminal communication network, the decomposition tree of a network provides the identity of the modules and an easily read map of the relations among them. The decomposition tree is derived by finding the triconnected components of the underlying graph. Reducing computation time by finding and analyzing the triconnected components of a network has been proposed for the reliability problems of 2-terminal communication, all-terminal communication, and feasible transportation flow. This paper introduces the use of the decomposition tree for reliability computation purposes, presents a general algorithm based on the tree, and demonstrates its application to the problems named above, as well as to the problem of feasible shortest path.
Keywords :
Communication networks; Computer networks; Inference algorithms; Reliability theory; State-space methods; Telecommunication network reliability; Terminology; Time measurement; Tree graphs; Decomposition tree; Modules; Network decomposition; Network reliability; Triconnected components;
fLanguage :
English
Journal_Title :
Reliability, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9529
Type :
jour
DOI :
10.1109/TR.1983.5221478
Filename :
5221478
Link To Document :
بازگشت