Minimal pathset and minimal cutsets using search technique

Abstract

Application of graph theory to reliability analysis was first made in 1970. Over the years, a large number of computer programmes have been developed to determine the spanning trees, the minimal paths and cutsets, which are essential for determining the reliability of the network. In recent years, there has been an interest in developing small desk top calculators for specific purposes, which could be used by the designers of transportation systems, communication systems, etc. In this article the authors present an approach to design a microprocessor based equipment to determine minimal pathset and minimal cutset from the incidence matrix of the graph. The authors have presented a new design approach, based on search technique. The salient feature of the new approach is a novel tracing process in which the desired graph is traced by operating a set of constraints. The new design approach has already been used by the authors to develop a microprocessor based spanning tree generator.