AN ALGORITHMIC APPROACH TO GRAPH ISOMORPHISM PROBLEM: INCREMENTAL ALGORITHM
Article Sidebar
Main Article Content
Abstract
Graph Isomorphism is a one-to-one and on-to mapping between two graphs so that the Properties of each vertex on one graph correspond to the properties of a vertex on the other graph. The graph isomorphism problem is a computational problem of determining whether two finite graphs are isomorphic or not. It is one of the small numbers of a problems belonging to NP neither known to be solvable in polynomial time nor NP complete. In this paper, I proposed an algorithm that determines whether two finite graphs are isomorphic or not.
Keywords: Direct Path Set Of Vertex, Set Intersection, Adjacency matrix, Null Set.
Downloads
Article Details
References
W. H. Tsai and K. S. Fu, “Error-correcting isomorphisms of attributed relational graphs for pattern analysis,†IEEE Trans. Syst., Man, Cybern., vol. SMC-9, pp. 757–768, Dec. 1979.
R. C. Read and D. G. Corneil, “The graph isomorphism disease,†J. Graph Theory, vol. 1, pp. 339–363, 1977.
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
K. A. De Jong and W. M. Spears, “Using genetic algorithms to solve NPcomplete problems,†in Proc. 3rd Int. Conf. Genetic Algorithms, George Mason Univ., Fairfax, VA, 1989, pp. 124–132.
J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: Univ. of Michigan Press, 1975.
L. Kitchen and A. Rosenfeld, “Discrete relaxation for matching relational structures,†IEEE Trans. Syst., Man, Cybern., vol. SMC-9, pp. 869–874, 1979.
L. Kitchen, “Relaxation applied to matching quantitative relational structures,†IEEE Trans. Syst., Man, Cybern., vol. SMC-10, pp. 96–101, Feb. 1980.
L. G. Shapiro and R. M. Haralick, “Structural descriptions and inexact matching,†IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-3, no. 5, pp. 504–519, 1981.
M. You and A. K. C. Wong, “An algorithm for graph optimal isomorphism,†in Proc. 1984 Int. Conf. Pattern Recognition, pp. 316–319.
S. U. Ama, “An eigendecomposition approach to weighted graph matching problems,†IEEE Trans. Pattern Anal. Machine Intell., vol. 10, no. 5, pp. 695–703, 1988.
J. J. Grefenstette, “Optimization of control parameters for genetic algorithms,†IEEE Trans. Syst., Man, Cybern., vol. SMC-16, pp. 122–128, Jan. 1986.
J. D. Schaffer, R. A. Caruana, L. J. Eshelman, and R. Das, “A study of control parameters affecting online performance of genetic algorithms for function optimization,†in Proc. 3rd Int. Conf. Genetic Algorithms, George Mason Univ., Fairfax, VA, 1989, pp. 51–60.
T. Back and F. Hoffmeister, “Extended selection mechanisms in genetic algorithms,†in Proc. 4th Int. Conf. Genetic Algorithms, Univ. California, San Diego, 1991, pp. 92–99.
T. Starkweather, S. McDaniel, K. Mathias, D. Whitely, and C. Whitely, “A comparison of genetic sequencing operators,†in Proc. 4th Int. Conf. Genetic Algorithms, Univ. California, San Diego, 1991, pp. 69–76.
K. A. DeJong, “An analysis of the behavior of a class of genetic adaptive systems,†Ph.D. dissertation, Univ. Michigan. Dissertation Abstr. Int., vol. 36, no. 10, p. 5140b, (University Microfilms 76-9381), 1975.
D. E. Goldberg and P. Segrest, “Finite Markov chain analysis of genetic algorithms,†in Proc. 2nd Int. Conf. Genetic Algorithms, Mass. Inst. Technol., Cambridge, MA, 1987, pp. 1–8.
W. H. Tsai and K. S. Fu, “Subgraph error-correcting isomorphisms for syntatic pattern recognition,†IEEE Trans. Syst., Man, Cybern., vol. SMC-13, pp. 48–62, Jan. 1983.
S. W. Lu, Y. Ren, and C. Y. Suen, “Hierarchical attributed graph representation and recognition of handwritten Chinese characters,†Pattern