Back to Search
Start Over
Algorithms for finding a fundamental set of cycles for an undirected linear graph
- Source :
- Communications of the ACM. 10:780-783
- Publication Year :
- 1967
- Publisher :
- Association for Computing Machinery (ACM), 1967.
-
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.
Details
- ISSN :
- 15577317 and 00010782
- Volume :
- 10
- Database :
- OpenAIRE
- Journal :
- Communications of the ACM
- Accession number :
- edsair.doi...........f0134189b0885b3415540239d1a128c7