Network reliability analysis using dual graph
Masahiro Hayashi · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1991
Abstract The problem of representing a communication network in a graph and evaluating the overall reliability is NP‐hard. The class of graphs called planar CF graphs is the maximum class whose exact overall reliability is confirmed as being possible to be evaluated by the polynomial order. In this paper, the dual graph to the given graph is constructed, and the overall reliability is evaluated. As a result, the following properties are obtained. The evaluation of the overall reliability is equivalent to the evaluation of the probability that a circuit exists in its dual graph (dual problem). The exact value of the dual problem can be evaluated by the reduction method. There exists a class of graphs which permits the evaluation of the overall reliability by the polynomial order using the method of property (2), and is larger than the Planar CF Graph (we call this extended class Planar Dual CF Graph).