Polynomial-time topological reductions that preserve the diameter constrained reliability of a communication network :un ambiente para el desarrollo de experimentos científicos

Abstract

In this paper, we propose a polynomial-time algorithm for detecting and deleting edges of a network which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may lead to important computational gains when combined with an exact method to calculate the reliability. Experimental results are shown, corroborating the predicted computational reward, when this reliability preserving algorithm is integrated within an exact factorization approach based upon Moskowitz\2019s edge decomposition theorem and applied to evaluate the Source-to-terminal Diameter Constrained reliability of specific topologies

En este trabajo se propone un algoritmo de tiempo polinomial para detectar y eliminar aristas de una red que son irrelevantes para el cálculo del parámetro de confiabilidad fuente-terminal con restricciones de diámetro en una red. Como la evaluación de este parámetro es un problema NP-difícil, el procedimiento propuesto puede resultar en una importante ganancia computacional cuando se combina con un método exacto para calcular la confiabilidad. Los resultados experimentales que se incluyen corroboran la ganancia computacional predicha, cuando el método de reducción es integrado dentro de un enfoque de factorización exacto, basado en el teorema de descomposición en aristas de Moskowitz, y utilizado para evaluar la confiabilidad con restricciones de dimetro de algunas topologías específicas.