A General Vertex Partition Refinement Algorithm for Graph Isomorphism

摘要：

　　A general depth-first backtracking algorithm for graph isomorphism with the vertex partition and refinement technique is presented in this paper.The time complexity of this nondeterministic polynomial algorithm is O(nα+3) where nα is the number of backtracking points and (h-l)/2≤α≤(h+l)/2 for h=logn in the worst cases.The tests on many types of graphs validated the efficiency of this algorithm for graph isomorphism.

关键词： component partition refinement invariant algorithm

作者: Aimin Hou Chuanfu Hu Zhifeng Hao

作者单位: Department of Computer Science,Dongguan University of Technology,Dongguan,523808,China School of Computer Science and Engineering,South China University of Technology,Guangzhou,510006,Chi

会议类型: 国际会议

会议名称: 2013 2nd international Conference on Opto-Electronics Engineering and Materials Eesearch(2013第二届光电工程与材料研究国际会议)(OEMR2013)

会议地点: 郑州

会议语种:英文

页码: 1764-1768

在线出版日期: 2013-10-19（万方平台首次上网日期，不代表论文的发表时间）