图同构中的一类顶点细分方法

摘要：

提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.

关键词：图同构、精确图同构、划分、稳定细分、顶点不变函数

所属期刊栏目：18

分类号：TP301(计算技术、计算机技术)

资助基金：中国科学院计算技术研究所资助项目20056600-4

在线出版日期：2007-04-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：213-219