Algebraic Aspects of Network Reliability Problems.

摘要

This research addresses both theoretical and computational aspects of evaluating the reliability of a complex system in terms of its structure and the reliability of its individual components. This type of problem frequently arises in the design and evaluation of telecommunication, logistics, and distribution systems, which are commonly modelled using networks. The present research employs an algebraic approach for studying the reliability of such network systems. This approach has not only unified a variety of theoretical results but has also produced a number of new algorithms for calculating various measures of system reliability. Based on this approach, both exact and approximate computational schemes have been developed, together with supporting data structures for implementing the necessary computations in an efficient manner. Approximation schemes, also based on an underlying algebraic structure, have also been developed for evaluating more general measures of system performance, such as average delay or throughput in stochastic systems. In addition this research has recently led to the study of efficient methods for generating cutsets in networks and has produced substantial improvements relative to existing methods for this fundamental task. (Author)