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

Majid Forghani-elahabad, Luiz Henrique Bonani

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.


Palavras-chave


Diophantine system, System reliability, Algorithm, d-MP , d-MC

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2015.003.02.0043

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato