Microprocessor Based Char's Tree Enumeration Algorithm

Abstract

Several algorithm have been proposed to enumerate all the spanning trees of a graph. This paper discusses a hardware implementation of Char's spanning tree enumeration algorithm using high speed digital integrated circuits. The implementation takes care of all the advantages offered by the Char's algorithm. Each node and its adjacent vertices are represented as a programmable digital circuitry and is modelled as a Mealy machine. A controller for the nodes gives out a signal when a tree is generated. This controller is connected to a microprocessor system in handshaking mode. This also controls the to and from communication between the digital circuitry and the microprocessor system.

Indexing terms:

• Tree enumeration
• Char's algorithm
• Microprocessor system