An Efficient Algorithm for Graph Isomorphism

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Efficient Algorithm for Graph Isomorphism

Full text

Pdf (768 KB)

Source

Journal of the ACM (JACM) archive
Volume 17 , Issue 1 (January 1970) table of contents

Pages: 51 - 64

Year of Publication: 1970

ISSN:0004-5411

Authors

D. G. Corneil	University of Toronto, Department of Computer Science, Toronto, Ontario, Canada
C. C. Gotlieb	University of Toronto, Department of Computer Science, Toronto, Ontario, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/321556.321562 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	LYNCH, M.F. Storage and retrieval of information on chemical structures by computer. Endeavour 27, 101 (May 1968), 68-73.
	2	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]
	3	SUSSENGUTH, E., JR. A graph theoretical algorithm for matching chemical structures. J. Chem. Doc. 5, 1 (Feb. 1965), 36-43.
	4	B~HM, C., AND SANTOLINI, A. A quasi-decision algorithm for the p-equivalence of two matrices. ICC Bull. 8, 1 (1964), 57-69.
	5	, CORNEIL, D.G. Graph Isomorphism. Ph.D. thesis, U. of Toronto, Canada, 1968.
	6	BOSE, R.C. Strongly regular graphs, partial geometries, and partially balanced designs. Pacific J. Math. 18 (1963), 389-420.
	7	GOETHALS, J. M., AND SEIDEL, J .J . Orthogonal matrices with zero diagonal. Canad. J. Math. 19 (1967), 1001-1010.
	8	SMOLENSKII, Y.A. A method for the linear recording of graphs. USSR Comput. Math. and Math. Phys. 2 (1963), 396-397.
	9	BUSACKER, R., AND SAATY, W. Finite Graphs and Networks--An Introduction with Applications. McGraw-Hill, New York, 1965, 196-199.
	10	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]

CITED BY 16

	José Soto , Jiří Fiala, Block transitivity and degree matrices, European Journal of Combinatorics, v.29 n.5, p.1160-1172, July, 2008
	Dexter Kozen, A clique problem equivalent to graph isomorphism, ACM SIGACT News, v.10 n.2, Summer 1978
	Gary L. Miller, On the nlog n isomorphism technique (A Preliminary Report), Proceedings of the tenth annual ACM symposium on Theory of computing, p.51-58, May 01-03, 1978, San Diego, California, United States
	A. Vince, Graph recurrence, European Journal of Combinatorics, v.24 n.1, p.15-32, 1 January 2003
	S. Mitchell , T. Beyer , W. Jones, Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs, Journal of the ACM (JACM), v.26 n.4, p.603-610, Oct. 1979
	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States
	J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976
	A. T. Berztiss, A Backtrack Procedure for Isomorphism of Directed Graphs, Journal of the ACM (JACM), v.20 n.3, p.365-377, July 1973
	Keith Paton, An algorithm for the blocks and cutnodes of a graph, Communications of the ACM, v.14 n.7, p.468-475, July 1971
	Sławomir Grzonkowski , Wojciech Zaremba , Maciej Zaremba , Bill McDaniel, Extending web applications with a lightweight zero knowledge proof authentication, Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology, October 28-31, 2008, Cergy-Pontoise, France
	Michael Hay , Gerome Miklau , David Jensen , Don Towsley , Philipp Weis, Resisting structural re-identification in anonymized social networks, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Yuanyuan Tian , Richard A. Hankins , Jignesh M. Patel, Efficient aggregation for graph summarization, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Douglas C. Schmidt , Larry E. Druffel, A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices, Journal of the ACM (JACM), v.23 n.3, p.433-445, July 1976
	Yuri Gurevich , Margus Veanes , Charles Wallace, Can abstract state machines be useful in language theory?, Theoretical Computer Science, v.376 n.1-2, p.17-29, May, 2007
	Bharat P. Dave , Niraj K. Jha, COFTA: Hardware-Software Co-Synthesis of Heterogeneous Distributed Embedded Systems for Low Overhead Fault Tolerance, IEEE Transactions on Computers, v.48 n.4, p.417-441, April 1999
	Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin