最大公共子图问题的约束符号求解技术
详细信息 查看官网全文
- 英文论文题名：Symbolic ADD algorithm of Weighted constraint Problem maximum common sub graph problem
- 论文作者：刘桂珍 ; 徐周波
- 英文论文作者：Liu Gui-Zhen ; XU Zhou-Bo ; Guangxi Key Laboratory of Trusted Software ; Guilin University of Electronic Technology
- 年：2016
- 作者机构：桂林电子科技大学广西可信软件重点实验室;
- 论文关键词：最大公共子图 ; 软约束满足问题 ; 全局约束 ; ADD
- 英文论文关键词：Maximum Common Induced Subgraph ; Soft Constraint Satisfaction Problem ; Global Constraint ; ADD
- 会议召开时间：2016-11-25
- 会议录名称：广西计算机学会2016年学术年会论文集
- 语种：中文
- 分类号：O157.5
- 学会代码：GXJH
- 会议名称：广西计算机学会2016年学术年会
- 会议地点：中国广西南宁
- 主办单位：广西计算机学会
- 学会名称：广西计算机学会
- 页数：7
- 文件大小：365k
- 原文格式：D
- 会议级别：地方
摘要
最大公共子图是非精确图匹配中一项重要的研究内容,但是如何快速而准确的找到两个图的最大公共子图是目前研究的难点。为此,文中建立了最大公共导出子图的Soft CSP模型,提出了代数决策图(ADD)的符号求解算法。首先,分别对两个图中的变量和值域进行编码,完成对两个图的ADD表示。其次,基于深度优先分支定界的算法思想,利用符号ADD的相关操作,实现对最大公共导出子图的求解。
the maximum common subgraph is an important research in terms of inexact graph matching, but it s the difficult point of the present study that find the maximum common subgraph of two graph. In this paper, we set up a soft CSP Soft model of the maximum common induced subgraph, and propose the symbolic ADD algorithm.First of all, respectively, we encoded the variables and domain of the two graghs, and expressed the two figure by using ADD. Secondly, based on the depth first branch and bound algorithm, we used the related operations of symbol ADD technology, solved the maximum common induced subgraph.
the maximum common subgraph is an important research in terms of inexact graph matching, but it s the difficult point of the present study that find the maximum common subgraph of two graph. In this paper, we set up a soft CSP Soft model of the maximum common induced subgraph, and propose the symbolic ADD algorithm.First of all, respectively, we encoded the variables and domain of the two graghs, and expressed the two figure by using ADD. Secondly, based on the depth first branch and bound algorithm, we used the related operations of symbol ADD technology, solved the maximum common induced subgraph.
引文
[1]于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.
[2]Levi G.A note on the derivation of maximal common subgraphs of two directed or undirected graphs[J].Calcolo,1973,9(4):341-352.
[3]Mcgregor J J.Backtrack search algorithms and the maximal common subgraph problem[J].Software Practice&Experience,1982,12(1):23-34.
[4]Krissinel E B,Henrick K.Common subgraph isomorphism detection by backtracking search[J].Software Practice&Experience,2004,34(34):591-607.
[5]Suters W H,Abu-Khzam F N,Zhang Y,et al.A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem[J].Lecture Notes in Computer Science,2005,3595(3595):717-727.
[6]Vismara P,Valery B.Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms[M]//Modelling,Computation and Optimization in Information Systems and Management Sciences.Springer Berlin Heidelberg,2008:358-368.
[7]FN Abukhzam,NF Samatova,MA Rizk,MA Langston,The Maximum Common Subgraph Problem:Faster Solutions via Vertex Cover,in AICCSA,2007,367~373
[8]Nirmala P,Lekshmi R S,Nadarajan R.Vertex cover-based binary tree algorithm to detect all maximum common induced subgraphs in large communication networks[J].Knowledge and Information Systems,2016,48(1):229-252.
[9]Ndiaye S N,Solnon C.CP Models for Maximum Common Subgraph Problems[M]//Principles and Practice of Constraint Programming–CP 2011.Springer Berlin Heidelberg,2011:637-644.
[10]Ndiaye S N.Searching for a maximum common induced subgraph by decomposing the compatibility graph[J].2016.
[11]徐周波,古天龙,常亮,等.加权约束满足问题的符号ADD求解算法[J].模式识别与人工智能,2011,24(1):14-21.
[12]于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.
[13]Bahar R I,Frohm E A,Gaona C M,et al.Algebric decision diagrams and their applications[J].Formal methods in system design,1997,10(2-3):171-206.
[14]H.Bunke and K.Sharer.A graph distance metric based on the maximal common subgraph.Pattern Recognition Letters,19(3):255{259,1998.
[15]J.W.Raymond and P.Willett.Maximum common subgraph isomorphism algorithms for the matching of chemical structures.Journal of computeraided molecular design,16(7):521{533,2002.
[16]Zampelli S.A Constraint Programming Approach to Subgraph Isomorphism[J].Deville Yves,2008.
[2]Levi G.A note on the derivation of maximal common subgraphs of two directed or undirected graphs[J].Calcolo,1973,9(4):341-352.
[3]Mcgregor J J.Backtrack search algorithms and the maximal common subgraph problem[J].Software Practice&Experience,1982,12(1):23-34.
[4]Krissinel E B,Henrick K.Common subgraph isomorphism detection by backtracking search[J].Software Practice&Experience,2004,34(34):591-607.
[5]Suters W H,Abu-Khzam F N,Zhang Y,et al.A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem[J].Lecture Notes in Computer Science,2005,3595(3595):717-727.
[6]Vismara P,Valery B.Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms[M]//Modelling,Computation and Optimization in Information Systems and Management Sciences.Springer Berlin Heidelberg,2008:358-368.
[7]FN Abukhzam,NF Samatova,MA Rizk,MA Langston,The Maximum Common Subgraph Problem:Faster Solutions via Vertex Cover,in AICCSA,2007,367~373
[8]Nirmala P,Lekshmi R S,Nadarajan R.Vertex cover-based binary tree algorithm to detect all maximum common induced subgraphs in large communication networks[J].Knowledge and Information Systems,2016,48(1):229-252.
[9]Ndiaye S N,Solnon C.CP Models for Maximum Common Subgraph Problems[M]//Principles and Practice of Constraint Programming–CP 2011.Springer Berlin Heidelberg,2011:637-644.
[10]Ndiaye S N.Searching for a maximum common induced subgraph by decomposing the compatibility graph[J].2016.
[11]徐周波,古天龙,常亮,等.加权约束满足问题的符号ADD求解算法[J].模式识别与人工智能,2011,24(1):14-21.
[12]于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.
[13]Bahar R I,Frohm E A,Gaona C M,et al.Algebric decision diagrams and their applications[J].Formal methods in system design,1997,10(2-3):171-206.
[14]H.Bunke and K.Sharer.A graph distance metric based on the maximal common subgraph.Pattern Recognition Letters,19(3):255{259,1998.
[15]J.W.Raymond and P.Willett.Maximum common subgraph isomorphism algorithms for the matching of chemical structures.Journal of computeraided molecular design,16(7):521{533,2002.
[16]Zampelli S.A Constraint Programming Approach to Subgraph Isomorphism[J].Deville Yves,2008.