In this paper we study the reliability of a network with two terminal nodes s and t, where its links are subject to random, independent failures (nodes are always operational), and the network is operating if the surviving edges allow the terminal nodes to be connected by a path of length bounded by a giving parameter D (corresponding to a constraint on communication time between those two nodes). In particular, we express the reliability of complete graph topologies (i.e. every pair of nodes of the network are adjacent), whose links belong to four different reliability classes, as a recursive formula of smaller networks and parameter D. The computational complexity of a direct implementation of a network with n nodes, is of order nD, which give us polynomial complexity for calculating the reliability for fixed values of D. This is an improvement over previous results since in general determining the reliability for the networks with two terminal nodes and fixed parameter D, was shown to be a NP-Hard problem [2]. In addition, this recursive formula can be applied for computing the reliability polynomial (i.e. the reliability expressed as a polynomial function of a unique link reliability) of complete networks.

En este trabajo se estudia la confiabilidad de una red con dos nodos terminales s y t, tal que sus líneas están sujetas a fallas aleatorias e independientes, y la red funciona si las líneas en funcionamiento permiten la conexión de los nodos terminales a través de un camino de largo acotado por un parámetro D (que permite modelar por ejemplo una restricción en el tiempo de comunicación entre estos nodos). En particular, se da la confiabilidad de redes de topología completa (es decir, donde todo par de nodos es adyacente) y cuyas líneas pertenecen a cuatro clases de confiabilidad diferente, como una fórmula recursiva en términos de un número de nodos más pequeños y parámetro D menor. La complejidad computacional de una implementación directa de la fórmula en una red con n nodos, es de orden nD, resultando en complejidad polinómica para valores fijos de x Esto es una mejora sobre los resultados pre-existentes, dado que en general determinar la confiabilidad de redes con dos nodos terminales y parámetro D fijo, es un problema NP-difícil [2]. Además, esta fórmula recursiva puede ser utilizada para calcular el polinomio de confiabilidad (es decir, la confiabilidad como función de una única confiabilidad de líneas) de grafos completos.