On the Minimum Common Supergraph of Two Graphs |
| |
| Authors: | Horst Bunke Xiaoyi Jiang Abraham Kandel |
| |
| Affiliation: | Department of Computer Science University of Bern Neubrückstrasse 10 CH-3012 Bern Switzerland e-mail: {bunke,jiang}@iam.unibe.ch, CH
Department of Computer Science and Engineering University of South Florida 4202 East Fowler Avenue Tampa, FL 33620-5399 USA e-mail: kandel@csee.usf.edu, US
|
| |
| Abstract: | The minimum common supergraph of two graphs, g1 and g2, is defined as the smallest graph that includes, as subgraphs, both g1 and g2. It is shown that minimum common supergraph computation can be solved by means of maximum common subgraph computation. For the latter problem, algorithms are known from the literature. It will also be shown that for a certain class of cost functions, the concept of graph edit distance is closely related with the minimum common supergraph. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
