Mean and maximum common subgraph of two graphs

被引：29

作者：

Bunke, H

Kandel, A

机构：

[1] Univ Bern, Inst Informat & Angew Math, CH-3012 Bern, Switzerland

[2] Univ S Florida, Dept Comp Sci & Engn, Tampa, FL 33620 USA

来源：

PATTERN RECOGNITION LETTERS | 2000年 / 21卷 / 02期

关键词：

edit distance; graph matching; maximum common subgraph; median graph; clustering;

D O I：

10.1016/S0167-8655(99)00143-9

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A mean of a pair of graphs, g(1) and g(2), is formally defined as a graph that minimizes the sum of edit distances to g(1) and g(2). The edit distance of two graphs g and g' is the minimum cost taken over all sequences of edit operations that transform g into g'. It will be shown that under a particular set of cost functions for any two graphs, g and g', a maximum common subgraph is a mean. Moreover, any subgraph of g or g' that contains a maximum common subgraph is a mean as well. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：163 / 168

页数：6

共 9 条

[1] [Anonymous], P NAT S PATT REC IM
[2] On a relation between graph edit distance and maximum common subgraph
Bunke, H
[J]. PATTERN RECOGNITION LETTERS, 1997, 18 (08) : 689 - 694
[3] Combinatorial search versus genetic algorithms:: A case study based on the generalized median graph problem
Bunke, H
Münger, A
Jiang, XY
[J]. PATTERN RECOGNITION LETTERS, 1999, 20 (11-13) : 1271 - 1277
[4] Levi G., 1973, CALCOLO, V9, P341, DOI [DOI 10.1007/BF02575586, 10.1007/bf02575586]
[5] LOPRESTI D, 1994, P INT WORKSH DOC AN, P191
[6] BACKTRACK SEARCH ALGORITHMS AND THE MAXIMAL COMMON SUBGRAPH PROBLEM
MCGREGOR, JJ
[J]. SOFTWARE-PRACTICE & EXPERIENCE, 1982, 12 (01) : 23 - 34
[7] RICE SV, 1992, ADV STRUCTURAL SYNTH, P333
[8] ORGANIZATION OF RELATIONAL MODELS FOR SCENE ANALYSIS
SHAPIRO, LG
HARALICK, RM
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1982, 4 (06) : 595 - 602
[9] STRING-TO-STRING CORRECTION PROBLEM
WAGNER, RA
FISCHER, MJ
[J]. JOURNAL OF THE ACM, 1974, 21 (01) : 168 - 173

← 1 →