An Efficient Algorithm for Isomorphic Problem on Generic Simple Graphs
Ngoc Bao Tran, Dinh Thuc Nguyen · 2008
Graph isomorphism has received considerable attention because of many of the practical applications of the problem. Also, researchers have not yet been able to discover where the graph isomorphism problem fits into the NP complexity model. In this paper, we establish necessary conditions for graph isomorphism problem. Based on these conditions, algorithms are proposed in order to solve the Graph Isomorphism problem in reasonable time. In the best-case time complexity for our algorithm is O(N) where N is the number of vertices. The proposed algorithm is applied to undirected simple graphs, i.e., graphs with undirected edges so that (u, v) and (v, u) are considered to be the same edge. This result can be used into authentication methods based on graph isomorphism.