计算机应用

作者：汪洋, 江世杰, 曹宇聪, 李传文

单位：东北大学 计算机科学与工程学院，沈阳 110169

关键词：GPU,编码树,轴心子图同构,子图同构,并行加速

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

来源：2022年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2022年第1期