A new spanning tree algorithm

Loading...
Thumbnail Image

Date

1974

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.

Description

Keywords

Citation

Collections