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

作     者：徐周波 梁轩瑜 刘华东 戴瑀君 XU Zhou-bo;LIANG Xuan-yu;LIU Hua-dong;DAI Yu-jun

作者机构：桂林电子科技大学广西可信软件重点实验室广西桂林541004 桂林电子科技大学机电工程学院广西桂林541004 

基　　金：国家自然科学基金项目(61762027、U1501252) 广西自然科学基金项目(2017GXNSFAA198172) 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2020年第41卷第2期

页      码：397-401页

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

主 题 词：子图同构 约束满足问题 对称性破坏 自同构 置换群 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2020.02.016

馆 藏 号：203883293...