A Backtrack Procedure for Isomorphism of Directed Graphs

ABSTRACT

A reasonably efficient procedure for testing pairs of directed graphs for isomorphism is important in information retrieval and other application fields in which structured data have to be matched. One such procedure, a backtrack procedure based on a representation of directed graphs by linear formulas, is described. A procedure for finding a partial subdigraph of a digraph that is isomorphic to a given digraph is also described.

REFERENCES

• 1: TURNER, J. Generahzed matrix functions and the graph isomorphmm problem. SIAM J. AppL Math. 16 (1968), 520-526.
• 2: SALTON, G , AND SUSSENGUTH, E.H. Some flexible reformation retrieval systems using structure matching procedures Proc AFIPS 1964 SJCC, Vol. 25, Spartan Books, New York, pp. 587-597
• 3: 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]
• 4: STEEN, J P. Principle d'un algorlthme de recherche d'un lsomorphlsme entre deux graphes. Rev. Frang Inf. Rech. Opdratwnelle 8, No. R-3 (1969), 51---69.
• 5: 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 [doi>10.1145/321556.321562]
• 6: CORNEAL, D. G. Graph Isomorphism. Ph.D. th., U. of Toronto, Toronto, Ontario, Canada, 1968.
• 7: Lee Krider, A Flow Analysis Algorithm, Journal of the ACM (JACM), v.11 n.4, p.429-436, Oct. 1964 [doi>10.1145/321239.321244]
• 8: BERZTISS, A. T , AND WATKINS, R.P. Directed graphs and automatic flowcharting. Proc. 4th Austral. Comp Conf., Adelaide, 1969, Griffin Press, Netley, South Australia, 1969, pp. 495- 499.
• 9: Alfs T. Berztiss , A. T. Berztiss, Data Structures: Theory and Practice, Academic Press, Inc., Orlando, FL, 1975
• 10: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 11: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 12: NAsH-WILLIAMS, C. ST J.A. Hamiltoman circuits in graphs and digraphs In The Many Facets of Graph Theory, G. Chartrand and S. F. Kapoor (Eds ), Sprmger-Verlag, Berhn-Heldelberg- New York, 1969, pp 237-243.
• 13: Patrick Krolak , Wayne Felts , George Marble, A man-machine approach toward solving the traveling salesman problem, Communications of the ACM, v.14 n.5, p.327-334, May 1971 [doi>10.1145/362588.362593]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Measurement, Performance, Theory