Algorithms for finding a fundamental set of cycles for an undirected linear graph
- 1 December 1967
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 10 (12) , 780-783
- https://doi.org/10.1145/363848.363861
Abstract
Given the adjacency matrix of the graph, the algorithm presented in this paper finds a spanning tree and then constructs the set of fundamental cycles. Our algorithm is slower than an algorithm presented by Welch by a ratio of N /3 ( N is the number of nodes) but requires less storage. For graphs with a large number of nodes and edges, when storage is limited our algorithm is superior to Welch's; however, when the graphs are small, or machine storage is very large, Welch's algorithm is superior. Timing estimates and storage requirements for both methods are presented.Keywords
This publication has 3 references indexed in Scilit:
- A Mechanical Analysis of the Cyclic Structure of Undirected Linear GraphsJournal of the ACM, 1966
- Toward a National Chemical Information Network.Journal of Chemical Documentation, 1965
- GIT—a heuristic program for testing pairs of directed line graphs for isomorphismCommunications of the ACM, 1964