摘要
提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.
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.
出处
《软件学报》
EI
CSCD
北大核心
2007年第2期213-219,共7页
Journal of Software
基金
中国科学院计算技术研究所青年基金No.20056600-4~~
关键词
图同构
精确图同构
划分
稳定细分
顶点不变函数
graph isomorphism
exact graph isomorphism
partition
stable refinement
vertex invariant
