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

A symbolic OBDD-based of constraint solving algorithm for subgraph isomorphism problem

作　　者：刘桂珍 徐周波 LIU Guizhen;XU Zhoubo(School of Computer and Information Security,Guilin University of Electronic Technology,Guilin 541004,China)

机构地区：[1]桂林电子科技大学计算机与信息安全学院

出　　处：《桂林电子科技大学学报》2019年第5期357-362,共6页Journal of Guilin University of Electronic Technology

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

摘　　要：针对求解子图同构问题计算复杂性较高的问题,提出了一种基于符号OBDD的子图同构约束求解算法(OBDD-SI)。该算法对子图同构进行CSP建模,采用OBDD对该模型进行隐式表示和刻画。结合OBDD符号操作技术和回溯算法进行求解,执行弧一致性技术对不满足约束的值进行过滤,从而得到子图同构的所有解。实验结果表明,本算法具有良好的求解性能。Aiming at the high computational complexity during solving the subgraph isomorphism problem,a symbolic OBDD-based of constraint solving algorithm for subgraph isomorphism problem(OBDD-SI)is proposed.First,the algorithm sets up CSP model for subgraph isomorphism,and uses OBDD to express and describe the model implicitly.Then,solving problem with the OBDD symbol operation technique and backtracking algorithm,and filter the values which do not satisfy the constraints by the arc consistency technique,thus all solutions of the subgraph isomorphism are obtained.Finally,the simulation results show that the OBDD-SI algorithm has good solution performance.

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

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]