Improved implementation of search technique to find spanning trees

Abstract

The authors have developed a set of algorithms to find the spanning trees, the minimal paths and minimal cutsets of a graph, starting from the incidence matrix of the graph. All the above algorithms employ a unique tracing process based on search techniques. The above algorithms have a number of salient features. The arithmetic and logic operations are very simple, which makes it possible to design small desk top calculators capable of handling reasonably large and complex graphs. The major constraint of these equipments is the memory capacity vis à vis their capability of handling larger graphs. The authors designed a microprocessor based system to find spanning trees. The end results were available in the form of code numbers of branches appearing in a spanning tree, which had to be noted down, every time a tree was generated. In the new system the end results are in a more compact form, i.e. the vectors (see definition), one vector for one tree. The user can easily note down the vectors and decode them later to obtain the branches of a tree. In the new system the user can reallocate the available working memory space to suit the problem. The memory requirement in the new approach is also less.