An Efficient Algorithm for Graph Isomorphism
Journal of the ACMPublished 1 January 1970Open access
Derek G. Corneil, C. C. Gotlieb
Citations332
SJR quartileQ1
SJR score2.25
SNIP3.16
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the re ordered graphs form a sufficiency condition for isomorphism; namely, if the reordered graphs are identical, then the given graphs are isomorphic.
Abstract
A procedure for determining whether two graphs are isomorphic is described. During the procedure, from any given graph two graphs, the representative graph and the reordered graph, are derived.
Keywords
Computer Science
Canadian Journal of MathematicsOrthogonal Matrices with Zero Diagonal
213 Citations1967J.-M. Goethals, J.J. Seidel
Journal of Chemical DocumentationA Graph-Theoretic Algorithm for Matching Chemical Structures.
150 Citations1965Edward H. Sussenguth
Communications of the ACMGIT—a heuristic program for testing pairs of directed line graphs for isomorphism
86 Citations1964Stephen H. Unger
GIT—Graph Isomorphism Tester—incorporates a variety of processes that attempt to narrow down the search for an isomorphism, or to demonstrate that none exists.
Communications of the ACMAlgorithms for finding a fundamental set of cycles for an undirected linear graph
42 Citations1967C. G. Gotlieb, Derek G. Corneil
The algorithm presented in this paper finds a spanning tree and then constructs the set of fundamental cycles and is slower than an algorithm presented by Welch by a ratio of N/3 (N is the number of nodes) but requires less storage.
Journal of Chemical DocumentationToward a National Chemical Information Network.
9 Citations1965Walter M. Carlson