文章基本信息

标题：A Practical Graph Isomorphism Algorithm with Vertex Canonical Labeling
本地全文：下载
作者：Hou, Aimin ; Zhong, Qingqi ; Chen, Yurou 等
期刊名称：Journal of Computers
印刷版ISSN：1796-203X
出版年度：2014
卷号：9
期号：10
页码：2467-2474
DOI：10.4304/jcp.9.10.2467-2474
语种：English
出版社：Academy Publisher
摘要：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 ^ a ) where n ^ a is the number of backtracking points and ( h -1)/2≤ a ≤( h +1)/2 for h =log ⁿ 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.
关键词：canonical labeling;graph isomorphism;backtracking algorithm;completeness;time complexity