DocumentCode
2786624
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
Volume
4
fYear
2011
fDate
24-25 Sept. 2011
Firstpage
309
Lastpage
311
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ICM.2011.245
Filename
6113755
Link To Document