DETERMINATION OF MINIMAL UPPER PATHS FOR RELIABILITY-ANALYSIS OF PLANAR FLOW NETWORKS

Abstract

Determination of minimal upper paths is an important step in calculating the reliability (i.e. the probability that a required amount of flow can be transmitted from a source to a terminal) of stochastic flow networks. This paper presents an algorithm for determining minimal upper paths of a planar flow network. Four criteria are developed to eliminate unnecessary subnetworks from the enumeration tree. CoMputational results indicate that the developed criteria are effective in reducing the number of explicitly considered subnetworks, and thereby, in reducing the amount of computational effort required. Minimal upper paths can be also utilized to calculate certain component importance measures or to identify the most reliable path for sending a required amount of flow from a source to a terminal.