An Algorithm for Graph Isomorphism Based on Path-length Numbers
Download as PDF
DOI: 10.23977/csic.2018.0944
Corresponding Author
Lijun Tian
ABSTRACT
This paper proposed an algorithm for graph isomorphism based on path-length number (AGIPN). AGIPN used Length-L path numbers as partition metrics which could divide not similar vertices into trivial cells easily. For those similar vertices, AGIPN took a dynamic mapping procedure. AGIPN was tested on graphs, such as random connected graphs, pseudo random k-regular graphs, regular rings, and regular 2D meshes. The results indicate that the time requirement of AGIPN do not increase exponentially with the graph size of all these types.
KEYWORDS
Graph Isomorphism, Algorithm, Path-Length Number