الفهرس | Only 14 pages are availabe for public view |
Abstract The development of reliable computer networks is becoming of increasing importance. One measure of two-terminal computer network reliability, termed probabilistic connectedness, is the probability that two specified computers could communicate. A standard model of a computer network is a graph in which nodes represent computers and branches represent links between computers. Edges are assumed to have statistically independent probabilities of failing and nodes are assumed to be perfectly reliable. Exact calculation of two-terminal reliability for general networks has been shown to be NP-complete. As a result it is desirable to compute upper and lower bounds that avoid the exponential computation likely required by exact algorithms. In this thesis, two methods are presented for computing the upper bounds for the two-terminal reliability. The frist method is based on wellknown node elimination technique. In this method all nodes between source node and target node are eliminated in one step. This is achieved by reducing the network to a two-terminal link between the source and target. |