Title :
Isomorphism Testing Algorithm Based on Dijkstra Algorithm for Plan Graphs
Author :
Liu, Shuiqiang ; Wu, Yanpeng
Author_Institution :
Network & Inf. Center, Shaoyang Univ., Shaoyang, China
Abstract :
Graph isomorphism problem is one of fundamental problems in graph theory. Proposed an isomorphism testing algorithm based on Dijkstra algorithm for plan graphs, and described how to imply Dijkstra algorithm to process distance matrix rapidly. The core idea of the algorithm is take distance vector-matrix as the only structure character representative of plan graphs. Theoretical analysis result shows proposed algorithm has time complexity of O(n^4), space complexity of O(n^2), and good application value.
Keywords :
computational complexity; graph theory; matrix algebra; Dijkstra algorithm; distance vector-matrix; graph isomorphism problem; isomorphism testing algorithm; plan graphs; space complexity; structure character representative; time complexity; Algorithm design and analysis; Computers; DNA; Educational institutions; Graph theory; Parallel algorithms; Testing; Dijkstra algorithm; graph isomorphism; plan graph;
Conference_Titel :
Information Technology, Computer Engineering and Management Sciences (ICM), 2011 International Conference on
Conference_Location :
Nanjing, Jiangsu
Print_ISBN :
978-1-4577-1419-1
DOI :
10.1109/ICM.2011.245
