Resumen

Este artículo extiende el conocido problema de la fuente más confiable (1-MRS) en grafos no confiables al problema de la 2-fuente más confiable (2-MRS). Se consideran dos tipos de modelos de probabilidad alcanzable de un par de nodos en grafos no confiables, es decir, la probabilidad superior y la probabilidad unida. El problema de 2-MRS tiene como objetivo encontrar un par de nodos en el grafo desde el cual el número esperado de nodos alcanzables o la mínima alcanzabilidad se maximiza. Tiene muchas aplicaciones importantes en redes informáticas o de comunicación no confiables a gran escala. La complejidad #P del problema 2-MRS en grafos generales se deduce directamente de la del problema 1-MRS. Este artículo trata de cuatro modelos del problema 2-MRS en árboles no confiables donde cada arista tiene una probabilidad de funcionamiento independiente y diseña un algoritmo de programación dinámica de tiempo cúbico y espacio cuadrático, respectivamente, para cada modelo.

• Materias:Modelado matemático Modelo de red neuronal Tasa de convergencia Aritmética Ondículas libres
• Subjects:Mathematical modeling Neural network model Convergence rate Arithmetic Free wavelets
• Palabras claves:Fuente confiable; Gráficos poco fiables; Modelos de probabilidad alcanzables; Par de nodos; Número esperado; Redes a gran escala
• Keywords:Reliable source; Unreliable graphs; Reachable probability models; Node pair; Expected number; Large-scale networks