2-PATH SUBSETS - EFFICIENT COUNTING AND APPLICATIONS TO PERFORMABILITY ANALYSIS

The problem of computing performability probabilities in stochastic PE RT and flow networks is studied when the network is ''minimally design ed'' to withstand any two component failures. Polynomial-time algorith ms to compute performability when the network is planar - the nonplana r versions being NP-hard - solve related ''two-path subset'' problems. Given an acyclic graph with weights on the arcs, the algorithms compu te the total weight of all subsets of arcs that are contained in (1) t wo source-sink paths, or (2) two are-disjoint source-sink paths. A pol ynomial algorithm is given for (1), and for (2) in the case where the graph is a source-sink planar k-flow graph, that is, edge-minimal with respect to supporting k units of flow. (C) 1998 Elsevier Science B.V. All rights reserved.