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

摘要：

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

关键词：子图同构、约束满足问题、有序二叉决策图、弧一致性

所属期刊栏目：39

分类号：TP391.4(计算技术、计算机技术)

资助基金：国家自然科学基金61762027;广西自然科学基金2017GXNSFAA198172;桂林电子科技大学研究生教育创新计划2017YJCX54 , 2017YJCX08

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

页数：共6页

页码：357-362