Education, Science, Technology, Innovation and Life
Open Access
Sign In

An Algorithm for Graph Isomorphism Based on Path-length Numbers

Download as PDF

DOI: 10.23977/csic.2018.0944

Author(s)

Lijun Tian

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

All published work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright © 2016 - 2031 Clausius Scientific Press Inc. All Rights Reserved.