Research and Advances

Algorithms for finding a fundamental set of cycles for an undirected linear graph

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.


Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved