基于对称破坏的子图同构约束求解算法

• 作者: 刘华东 徐周波 戴瑀君 梁轩瑜
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 子图同构 约束满足问题 对称性破坏 自同构 置换群
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 软件与算法
• 页码范围: 397-401
• 页数: 5页
• 分类号: TP301
• 字数: 4642字
• 语种: 中文
• DOI: 10.16208/j.issn1000-7024.2020.02.016

摘要

为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法.基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(CSP)模型,结合CSP的回溯算法对其求解.实验结果表明,该算法有效减少了对重复解的搜索,与传统算法相比明显提高了搜索效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘华东	桂林电子科技大学广西可信软件重点实验室	13	66	4.0	8.0
5	徐周波	桂林电子科技大学广西可信软件重点实验室	53	284	8.0	15.0
6	戴瑀君	桂林电子科技大学广西可信软件重点实验室	2	0	0.0	0.0
7	梁轩瑜	桂林电子科技大学广西可信软件重点实验室	1	0	0.0	0.0