ALGORITHMS FOR APPROXIMATE GRAPH MATCHING

被引：21
作者：
WANG, JTL [1 ]
ZHANG, KZ [1 ]
CHIRN, GW [1 ]
机构：
[1] UNIV WESTERN ONTARIO,DEPT COMP SCI,LONDON,ON,CANADA
来源：
INFORMATION SCIENCES | 1995年 / 82卷 / 1-2期
基金：
美国国家科学基金会; 加拿大自然科学与工程研究理事会;
关键词：
D O I：
10.1016/0020-0255(94)00057-I
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete, and relabel the nodes and edges) to transform one graph to the other. The paper considers two variants of the approximate graph matching problem (AGM): Given a pattern graph P and a data graph D: 1. What is the distance between P and D? 2. What is the minimum distance between P and D when subgraphs can be freely removed from D? We first show that no efficient algorithm can solve either variant of the AGM unless P = NP. Then we present several heuristic algorithms leading to approximate solutions. The heuristics are based on probabilistic hill climbing and maximum flow techniques. Our experimental results involving the comparison of real and simulated data demonstrate the good performance of the algorithms presented.
引用
收藏
页码：45 / 74
页数：30
相关论文
共 50 条
[1]  
ACKLEY DH, 1985, COGNITIVE SCI, V9, P147
[2]  
Aho A., 1983, DATA STRUCTURES ALGO
[3]  
ARAGON CR, 1984, UNPUB OPTIMIZATION S
[4]  
Fu K.S., 2019, APPL PATTERN RECOGNI
[5]  
GALIL Z, 1990, SIAM J COMPUT, V119, P989
[6]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[7]   THE SYNTHESIS OF 2-PYRIMIDINONE NUCLEOSIDES AND THEIR INCORPORATION INTO OLIGODEOXYNUCLEOTIDES [J].
GILDEA, B ;
MCLAUGHLIN, LW .
NUCLEIC ACIDS RESEARCH, 1989, 17 (06) :2261-2281
[8]  
HAO X, 1993, 2ND P INT C DOC AN R, P319
[9]  
HAO XL, 1993, FIFTH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, TAI '93, PROCEEDINGS, P427, DOI 10.1109/TAI.1993.633991
[10]  
Hunter L., 1993, ARTIFICIAL INTELLIGE
12345