Simple novel algorithm for a special diophantine system appeared in the system reliability problem

Resumo

System reliability of a stochastic-flow network (SFN) can be computed in terms of either upper boundary points for demand level d called d-minimal cuts (d-MCs) or lower boundary points for demand level d called d-minimal paths (d-MP s). A number of different algorithms have been proposed in the literature to search for and determine all the d-MCs or d-MP s in an SFN. Majority of those algorithms need to solve a special Diophantine system. Here, we consider the Diophantine system appeared in d-MC and d-MP problems and propose a novel efficient algorithm to solve it. The proposed algorithm finds all the system solutions in a increasing lexicographic order. We illustrate the algorithm through an example and show its time complexity to be linear according to the number of its solutions.