Graph Isomorphism in View of Decomposition Technique
Krishnendu Basuli1, Sonali Das2
1Krishnendu Basuli, Dept. Of Computer Science, West Bengal State University,Barasat, Kolkata-126, West Bengal, India.
2Sonali Das, Department of Laboratory Medicine, Calcutta School of Tropical Medicine, 108, C. R. Avenue, Kolkata, India.
Manuscript received on November 22, 2019. | Revised Manuscript received on December 15, 2019. | Manuscript published on December 30, 2019. | PP: 4773-4777 | Volume-9 Issue-2, December, 2019. | Retrieval Number: B2687129219/2019©BEIESP | DOI: 10.35940/ijeat.B2687.129219
Open Access | Ethics and Policies | Cite | Mendeley
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Graph Isomorphism is anopen problem in graph theory. A large number of graphs have the polynomial time algorithms for detection. But in general there are specific algorithms for certain range of vertices. Our try to design a generic algorithm. In this paper we proposed an algorithm of O(n3 ) complexity. The decomposition techniques have been adopted as well as reconstruction conjecture in reverse for taking decision of whether the two graphs are isomorphic or not.The ideology is inherited from DNA isolation in molecular biology [Chomczynski et. al].
Keywords: Graph, Isomorphism, reconstruction, Conjec-ture, graph decomposition, DNA isolation.