AN ALGORITHMIC APPROACH TO GRAPH ISOMORPHISM PROBLEM: INCREMENTAL ALGORITHM

Article Sidebar

pdf
Published: Mar 31, 2013

Main Article Content

Dharmaiah Gurram

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

Download data is not yet available.

Article Details

How to Cite
Gurram, D. (2013). AN ALGORITHMIC APPROACH TO GRAPH ISOMORPHISM PROBLEM: INCREMENTAL ALGORITHM. Journal of Global Research in Mathematical Archives(JGRMA), 1(3), 16–23. Retrieved from https://www.jgrma.com/index.php/jgrma/article/view/38
Issue
Vol. 1 No. 3 (2013): March-2013
Section
Research Paper

Open Access: This is an open-access journal. All articles published in the Journal of Global Research in Mathematical Archives(JGRMA) are made immediately and permanently available under the Creative Commons Attribution 4.0 International (CC BY 4.0) License. Authors retain the copyright of their work and grant Journal of Global Research in Mathematical Archives(JGRMA)  the right of first publication. This license permits unrestricted use, distribution, adaptation, and reproduction in any medium or format, including commercial use, provided the original author(s), source, and license are properly acknowledged.

Google Scholar Indexed | DOI Enabled | OAI-PMH Compliant | Open Access Journal

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