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

• 作者: 刘桂珍 徐周波
• 来源期刊: 桂林电子科技大学学报
• 学科: 工学
• 关键词: 子图同构 约束满足问题 有序二叉决策图 弧一致性
• 年，卷（期）: 2019,（5）
• 页码范围: 357-362
• 页数: 6页
• 分类号: TP391.4
• 字数: 5796字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-808X.2019.05.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐周波	桂林电子科技大学计算机与信息安全学院	53	284	8.0	15.0
2	刘桂珍	桂林电子科技大学计算机与信息安全学院	3	2	1.0	1.0