基于符号OBDD的子图同构约束求解算法

作者:刘桂珍; 徐周波*
来源:桂林电子科技大学学报, 2019, 39(05): 357-362.
DOI:10.16725/j.cnki.cn45-1351/tn.2019.05.003

摘要

针对求解子图同构问题计算复杂性较高的问题,提出了一种基于符号OBDD的子图同构约束求解算法(OBDD-SI)。该算法对子图同构进行CSP建模,采用OBDD对该模型进行隐式表示和刻画。结合OBDD符号操作技术和回溯算法进行求解,执行弧一致性技术对不满足约束的值进行过滤,从而得到子图同构的所有解。实验结果表明,本算法具有良好的求解性能。