Applying Parallelism to Calculate the Number of Path-Sets and Cut-Sets of a Graph with Restricted Diameter Based on Construction-Destruction Methods

摘要

Consider a probabilistic graph G comprising a node-set V, an edge-set E, and where K € Vis a set of nodes called the terminal nodes. The edges of the network fail independently with known probabilities and nodes are perfectly reliable. We present a Monte Carlo Construction technique to evaluate the number of sub-graphs of G, called the d- path-sets of G, in which the distance between terminals is less or equal a given integer value d. Calculation of the number of d-path-sets permit us to evaluate the Diameter Constrained Reliability of a network , an extension of the classical reliability, both known to be intractable problems; because of this intractability these Monte Carlo methods are applied and embedded within a distributed/parallel environment, using MPI libraries. Construction-Destruction methods in combination with parallel computing, provide accurate estimates.