Determinação dos k Caminhos Mínimos Disjuntos Mais Confiáveis em Uma Rede de Fluxo Multiestado

A determinação de k caminhos mínimos disjuntos (CMDs) em uma rede de fluxo multi-estado (RFM) desempenha um papel fundamental na garantia da confiabilidade e disponibilidade de sistemas reais, como telecomunicações, transporte e redes de distribuição. Embora estudos anteriores tenham se concentrado na identificação do número máximo de CMDs entre dois nós em um grafo, a confiabilidade dos caminhos selecionados em uma RFM tem sido pouco explorada. Neste trabalho, introduzimos o problema de determinar os k CMDs mais confiáveis capazes de transmitir d unidades de fluxo de uma fonte a um destino dentro de T unidades de tempo. Além disso, propomos um algoritmo para sua resolução e demonstramos sua correção.