Improved implementation of search technique to find spanning trees

Bansal, V. K. ; Misra, K. B. ; Jain, M. P. (1983) Improved implementation of search technique to find spanning trees Microelectronics Reliability, 23 (1). pp. 141-147. ISSN 0026-2714

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:20030
Deposited On:20 Nov 2010 15:08
Last Modified:07 Jun 2011 06:49

Repository Staff Only: item control page