Reducibility of stochastic networks

This paper deals with the problem of reducing a stochastic network to one equivalent activity. The problem was motivated by the question of determining or approximating the probability distribution function of the duration of the longest or shortest path in a stochastic network. We define a particular reduction and use it to characterize the reducibility of such a network. The network can be reduced to one equivalent activity if the network does not have a special graph which we call the ‘interdictive graph’, or IG for short. If an IG is embedded in the network, the network is irreducible. In this case, its reduction becomes possible by duplicating some of the arcs in the irreducible network. The concept of duplicating an arc is introduced, then it is used to identify the arcs which can be duplicated. The reduction procedure is stated and illustrative examples are provided. An upper bound on the number of duplications is established.