Isomorphism Testing Algorithm Based on Dijkstra Algorithm for Plan Graphs
Shuiqiang Liu, Yanpeng Wu · 2011
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.