chapter  8
26 Pages

Algorithmic Aspects of Network Reliability

An explicit formula is from the mathematical point of view the most satisfying solution of a problem. As an example, the reliability polynomial of a cycle, R(Cn; p) = p

n + npn1(1 p), is such a nice result. However, we may …nd rarely any problems in engineering applications that exhibit such closed-form solutions. Often we look for an algorithm that solves a general class of problems. Clearly we expect in the …rst place that the algorithm works correctly for any intended input. The input may be a graph from a well-prescript class of graphs (e.g. an undirected connected …nite graph) and a set of parameters such as edge reliabilities. An answer can be a reliability polynomial or a numerical value for the desired reliability measure. In the latter case, we enter …rst di¢ culties in deciding what “a correct answer”means. Processing numerical data with computers always produces errors. If these errors are small enough then we will be willing to accept them. Numerical errors are usually not the hardest obstacle in reliability analysis, since in most cases we do not need a great number of iterations.