Volume 9 Number 10 (Oct. 2014)
Home > Archive > 2014 > Volume 9 Number 10 (Oct. 2014) >
JCP 2014 Vol.9(10): 2467-2474 ISSN: 1796-203X
doi: 10.4304/jcp.9.10.2467-2474

A Practical Graph Isomorphism Algorithm with Vertex Canonical Labeling

Aimin Hou1, Qingqi Zhong1, Yurou Chen1, and Zhifeng Hao2
1School of Computer, Dongguan University of Technology, Dongguan 523808, China
2Faculty of Computer, Guangdong University of Technology, Guangzhou 510006, China

Abstract—The vertex canonical labeling technique is one of the powerful methods in solving the graph isomorphism problem. However, some famous algorithms relied upon this technique are incomplete due to their non-zero probability of rejection. In this paper, we advance a new method of vertex canonical labeling and propose a complete graph isomorphism algorithm with depth-first backtracking. The time complexity of this algorithm is O(n^α) where n^α is the number of backtracking points and (h-1)/2≤α≤(h+1)/2 for h=logn in most cases. Finally, the proposed algorithm is compared with other researches on many types of graphs. The performance results validated that our algorithm is efficient for a wide variety of families of graphs.

Index Terms—canonical labeling; graph isomorphism; backtracking algorithm; completeness; time complexity

[PDF]

Cite: Aimin Hou, Qingqi Zhong, Yurou Chen, and Zhifeng Hao, "A Practical Graph Isomorphism Algorithm with Vertex Canonical Labeling," Journal of Computers vol. 9, no. 10, pp. 2467-2474, 2014.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>