A new spanning tree algorithm
Loading...
Files
Date
1974
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The algorithm outlined in this paper finds all the spanning trees of a non-directed graph G. The graph is represented by a binary incidence matrix using compact bit storage. Each row of the matrix corresponds to a branch of the graph and is represented by one or more computer words. Each column of the matrix corresponds
to a graph node and is represented by a single bit within each computer word or multiple word. It is shown, in addition to saving computer storage, that this representation greatly speeds up the tree generation process by allowing many bit-parallel operations to occur during the execution of a single computer instruction
cycle.