| 摘要: |
| 提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果. |
| 关键词: 图同构 精确图同构 划分 稳定细分 顶点不变函数 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the Youth Foundation of Institute of Computing Technology, the Chinese Academy of Sciences under Grant No.20056600-4 (中国科学院计算技术研究所青年基金) |
|
| A Vertex Refinement Method for Graph Isomorphism |
|
ZOU Xiao-Xiang,DAI Qiong
|
| Abstract: |
| In this paper, a vertex refinement method is proposed. The new vertex invariant is defined based on the number of the paths for a given length. A comparison between this vertex invariant and some other general vertex invariants has been made. It is proved that this method is as fine as other methods, and examples are given to show that this method is better than others in some case. This vertex refinement method can be used in graph isomorphism algorithms to reduce the number of mapping between the vertexes. |
| Key words: graph isomorphism exact graph isomorphism partition stable refinement vertex invariant |
