A problem encountered in the analysis of communication and other distribution systems is evaluating the performance of the system in meeting user demands with available resources. We consider the case in which user demands and available resources are only known stochastically and connecting links can operate at various levels. This situation can be modeled as a two-terminal stochastic network flow problem, in which each edge of the network assumes a finite number of values (corresponding to different capacity levels) with known probabilities. For each state of the network, we are interested in the maximum demand that can be met using the best allocation of resources. The approach used here to estimate the average unmet demand involves generating only “high leverage” states of the system—states having high probability and/or high values of unmet demand. A new algorithm is proposed for generating such states in monotone order, either by probability or by unmet demand. Bounds on the performance of the network are investigated.

The empirical performance of state enumeration methods proposed by several authors are examined, and refinements which result in significant computational improvements are presented. Two methods for state enumeration which compare favorably with the most efficient of current methods are introduced. They are based respectively on the work of S.-N. Chiou and V.O.K. Li (1986) and R.F. Gaebler and R.J. Chen (1987). It is shown that every algorithm discussed except that of C.L. Yang and P. Kubar (1989) can be executed significantly faster when the state enumeration problem is somewhat relaxed.>

The two-terminal reliability problem for an undirected network involves calculating the probability that two distinguished sites are connected by a path of working edges. This problem is known to be NP-hard, even for the special case of planar systems. We present efficient data structures and algorithms for manipulating planar networks and for generating both paths an cutsets in such networks. A pseudopolynomial algorithm is then implemented, based on these generation procedures, to calculate two-terminal reliability for planar networks; that is, the algorithm's time complexity is polynomially bounded in the number of paths (or the number of cutsets). Computational experience with this implementation is also presented, showing that it provides a substantial improvement over previous implementations of the pseudopolynomial algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The problem of determining a minimum spanning tree arises in a number of application areas, including network reliability, pattern recognition, clustering, and design of distribution systems.The present algorithm implements Prim's procedure [7] for calculating a minimum spanning tree in an undirected network when the edge costs can be scaled to integers in a moderate range.While other codes for implementing Prim's procedure have been published [4,6,8, 9], all have used a two-dimensional array for storing the edge costs.As a result, such implementations have been limited to fairly small networks (e.g., 100 or fewer vertices).Moreover, these previous codes do not take advantage of network sparsity to reduce the computational effort.In contrast, the present code does exploit network sparsity and has been used to calculate minimum spanning trees for networks with up to 500 vertices and 24,000 edges.Even such large problems required less than 0.7 seconds of CPU time on an IBM 370/3033 computer (IBM Extended H FORTRAN compiler).For the algorithm given here, the edge costs are assumed to be positive integers with maximum edge cost CMAX.The network, assumed to be connected with NV vertices, is represented in forward star form [2,3].That is, for each vertex i E {1 ..... NV}, EPT(i) is a pointer to the first position in a list ELIST where the vertices j adjacent to i are stored consecutively.A list ECOST, of the same size as ELIST, stores the corresponding edge costs c(i, j) for the edges (i, j).It