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 [J].