A Dynamic Mapping Algorithm for Graph Isomorphism

摘要：

The graph isomorphism problem is still an open question if it is NP-Complete or not. This paper proposed a dynamic mapping algorithm for graph isomorphism (DMAGI). DMAGI used Length-L path numbers as partition metrics which could divide not similar vertices into trivial cells easily. For those similar vertices, DMAGI took a dynamic mapping procedure. DMAGI 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 DMAGI dont increase exponentially with the graph size of all these types.

关键词： graph isomorphism algorithm DMAGI dynamic mapping pattern recognition

作者: Lijun Tian Chaoqun Liu Jianquan Xie

作者单位: Information Technology Department Hunan University of Finance and Economics No. 139, Fenglin 2nd Road, Changsha, 410205, China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer and Automation Engineering(ICCAE 2011)(2011年第三届IEEE计算机与自动化工程国际会议)

会议地点: 重庆

会议语种:英文

页码: 241-244

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