ISSN:
1572-9338
Keywords:
Reliability coefficient
;
network reliability
;
communications network
;
ramification index
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract The most common idea of network reliability in the literature is a numerical parameter calledoverall network reliability, which is the probability that the network will be in a successful state in which all nodes can mutually communicate. Most papers concentrate on the problem of calculating the overall network reliability which is known to be an NP hard problem. In the present paper, the question asked is how to find a method for determining a reliable subnetwork of a given network. Givenn terminals and one central computer, the problem is to construct a network that links each terminal to the central computer, subject to the following conditions: (1) each link must be economically feasible; (2) the minimum number of links should be used; and (3) the reliability coefficient should be maximized. We argue that the network satisfying condition (2) is a spanning arborescence of the network defined by condition (1). We define the idea of thereliability coefficient of a spanning arborescence of a network, which is the probability that a node at average distance from the root of the arborescence can communicate with the root. We show how this coefficient can be calculated exactly when there are no degree constraints on nodes of the spanning arborescence, or approximately when such degree constraints are present. Computational experience for networks consisting of up to 900 terminals is given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02022045
Permalink
