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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (433 KB)

Source

Communications of the ACM archive
Volume 10 , Issue 12 (December 1967) table of contents

Pages: 780 - 783

Year of Publication: 1967

ISSN:0001-0782

Authors

C. G. Gotlieb	Univ. of Toronto, Toronto, Canada
D. G. Corneil	Univ. of Toronto, Toronto, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 74, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/363848.363861 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BERGE, C. The Theory of Graphs and Its Applications. John Wiley, New York, 1962.
	2	BUSACKER, R., AND SAATY, W. Finite Graphs and Networks- An Introduction with Applications, McGraw-Hill, New York, 1965, pp. 99-109.
	3	Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
	4	SUSSENGUTH, E., JR. A graph theoretical algorithm for matching chemical structures. J. Chem. Doc. 5, 1 (Feb. 1965), 36-43.
	5	Stephen H. Unger, GIT—a heuristic program for testing pairs of directed line graphs for isomorphism, Communications of the ACM, v.7 n.1, p.26-34, Jan. 1964 [doi>10.1145/363872.363899]
	6	John T. Welch, Jr., A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs, Journal of the ACM (JACM), v.13 n.2, p.205-210, April 1966 [doi>10.1145/321328.321331]

CITED BY 8

	Norman E. Gibbs, A Cycle Generation Algorithm for Finite Undirected Linear Graphs, Journal of the ACM (JACM), v.16 n.4, p.564-568, Oct. 1969
	Joseph E. Grimes, Scheduling to reduce conflict in meetings, Communications of the ACM, v.13 n.6, p.351-352, June 1970
	James C. Tiernan, An efficient search algorithm to find the elementary circuits of a graph, Communications of the ACM, v.13 n.12, p.722-726, Dec. 1970
	Narsingh Deo , G. Prabhu , M. S. Krishnamoorthy, Algorithms for Generating Fundamental Cycles in a Graph, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.26-42, March 1982
	Keith Paton, An algorithm for finding a fundamental set of cycles of a graph, Communications of the ACM, v.12 n.9, p.514-518, Sept. 1969
	Pentti A. Honkanen, Circuit enumeration in an undirected graph, Proceedings of the 16th annual Southeast regional conference, p.49-53, April 13-15, 1978, Atlanta, Georgia
	D. G. Corneil , C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, Journal of the ACM (JACM), v.17 n.1, p.51-64, Jan. 1970
	Peng-Siu Mei , Norman E. Gibbs, A planarity algorithm based on the Kuratowski theorem, Proceedings of the May 5-7, 1970, spring joint computer conference, May 05-07, 1970, Atlantic City, New Jersey