摘要: 子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题。针对现在已经有许多高效的子图同构算法,但是对于轴心子图同构问题目前并没有基于GPU的搜索算法,而通过改造子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出一种基于GPU的轴心子图同构算法。首先,通过一种新颖的多编码树方式,利用节点的标签、度以及节点邻居的结构特征组合对节点进行编码,在GPU上对查询图节点并行地进行剪枝,明显减小了数据图候选节点所生成的搜索空间树的尺寸;然后,逐层访问查询图节点的候选节点,过滤掉不满足的节点;最后验证得到的子图是否是查询图的同构子图,从而高效地完成轴心子图同构搜索。实验结果表明,与GPU友好子图匹配(GpSM)算法相比,算法执行时间降低了二分之一,能够高效地执行轴心子图同构搜索并且具有可扩展性。轴心子图同构算法的提出可以减少解决轴心子图同构问题所需的时间,同时降低了GPU内存消耗,提升了算法的性能。
中图分类号: