Algorithms for Generating Fundamental Cycles in a Graph

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for Generating Fundamental Cycles in a Graph

Full text

Pdf (899 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 8 , Issue 1 (March 1982) table of contents

Pages: 26 - 42

Year of Publication: 1982

ISSN:0098-3500

Authors

Narsingh Deo	Computer Science Department, Washington State University, Pullman, WA
G. Prabhu	Computer Science Department, Washington State University, Pullman, WA
M. S. Krishnamoorthy	Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 108, Citation Count: 6

Additional Information:

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/355984.355988 What is a DOI?

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	CORNEIL, D B., AND READ, R C. The graph isomorphism disease J Gr. Theory I (1977), 339- 363.
	3	DF~O, N. Graph Theory wtth Applwattons to Engtneertng and Computer Science. Prentice- Hall, Englewood Cliffs, N J., 1974.
	4	DEO, N. Breadth and depth first searches in graph theoretic algorithms J. Comput. Soc India 4 (1974), 1-8.
	5	DEo, N. Minimum-length fundamental cycle set. IEEE Trans. Cwcuits Systems CAS~26 (Oct 1979), 894-895.
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	Norman E. Gibbs, Basic cycle generation [H], Communications of the ACM, v.18 n.5, p.275-276, May 1975 [doi>10.1145/360762.360778]
	8	C. G. Gotlieb , D. G. Corneil, Algorithms for finding a fundamental set of cycles for an undirected linear graph, Communications of the ACM, v.10 n.12, p.780-783, Dec. 1967 [doi>10.1145/363848.363861]
	9	HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass, 1969.
	10	HUBICKA, E., AND SYSLO, M.M. Minimal bases of cycles of a graph. In Proc 2nd Czechoslovak Symp. Graph Theory. Academia (Prague, 1975), pp. 283-293.
	11	Tetsuro Ito , Makoto Kizawa, The Matrix Rearrangement Procedure for Graph-Theoretical Algorithms and Its Application to the Generation of Fundamental Cycles, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.227-231, Sept. 1977 [doi>10.1145/355744.355746]
	12	JOHSSON, D.S., LENSTRA, J.D., AND R1NNOOY KAN, A.H.G. The complexity of the network design problem. Networks 8 (1978).
	13	JOVANOVICH, A.D. Note on a modification of the fundamental cycle finding algorithm. Inf. Process. Lett. 3 (July 1974).
	14	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	15	KOLASINSKA, E. On a minimum cycle basis of a graph. Zastosow Matem 16 (1980), 631-639.
	16	LEDER~.RG, J. Topology of Molecules. Mathematwal Sciences, M.I.T. Press, Cambridge, Mass., 1968, 37-51.
	17	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 [doi>10.1145/363219.363232]
	18	Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
	19	STEPANEC, G.F. Basis systems of vector cycles with extremal properties in graphs (m Russian), Usp. Mat. Nauk 19, 2 (116) (1964), 171-175.
	20	SUSSENGUTH, E., JR. A graph theoretical algorithm for matching chemical structures. J. Chem. Doc. 5, 1 (Feb. 1965), 36-43.
	21	SYSLO~ M.M. Fundamental set of cycles of a graph. Zastosow Matem 13 (1973), 399-409.
	22	SYSLO, M.M. Minimum-length cycle bases of a graph (Extended Abstract). Methods Oper. Res. 37 (1980), 385-390.
	23	TA~AN, R.E. Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972), 146- 160.
	24	TINHOFER, G. Zufallsgraphen. Hanser, Munich, 1980.
	25	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]
	26	Z'~KOV, A.A. Theory of Fmae Graphs (in Russmn). Nauka, Novosibirsk, 1969.

CITED BY 6

	Michael Philippsen, Automatic alignment of array data and processes to reduce communication time on DMPPs, ACM SIGPLAN Notices, v.30 n.8, p.156-165, Aug. 1995
	Siddarameshwar Bagali , Warren N. Waggenspack, Jr., A shortest path approach to wireframe to solid model conversion, Proceedings of the third ACM symposium on Solid modeling and applications, p.339-350, May 17-19, 1995, Salt Lake City, Utah, United States
	Christian Liebchen , Romeo Rizzi, Classes of cycle bases, Discrete Applied Mathematics, v.155 n.3, p.337-355, February, 2007
	M. De la Sen , A. Ibeas, On the stability properties of linear dynamic time-varying unforced systems involving switches between parameterizations from topologic considerations via graph theory, Discrete Applied Mathematics, v.155 n.1, p.7-25, 1 January 2007
	C. J. Eqvhazy , T. B. Ramsay, Generating a set of fundamental cycles in a graph, ACM SIGACT News, v.17 n.1, p.78-82, June 1985
	Christian Liebchen , Gregor Wünsch, The zoo of tree spanner problems, Discrete Applied Mathematics, v.156 n.5, p.569-587, March, 2008