Graph matching by relaxation of fuzzy assignments

Author

Medasani, Swarup ; Krishnapuram, Raghu ; Choi, YoungSik

Author_Institution

HRL Lab., Malibu, CA, USA

Volume

9

Issue

1

fYear

2001

fDate

2/1/2001 12:00:00 AM

Firstpage

173

Lastpage

182

Abstract

Graphs are very powerful and widely used representational tools in computer applications. We present a relaxation approach to (sub)graph matching based on a fuzzy assignment matrix. The algorithm has a computational complexity of O(n²m²) where n and m are the number of nodes in the two graphs being matched, and can perform both exact and inexact matching. To illustrate the performance of the algorithm, we summarize the results obtained for more than 12 000 pairs of graphs of varying types (weighted graphs, attributed graphs, and noisy graphs). We also compare our results with those obtained using the graduated assignment algorithm

Keywords

computational complexity; fuzzy set theory; graph theory; matrix algebra; pattern matching; attributed graphs; exact matching; fuzzy assignment matrix; graduated assignment algorithm; graph matching; inexact matching; noisy graphs; relaxation approach; weighted graphs; Computational complexity; Computer applications; Helium; Joining processes; Knowledge representation; Laboratories; Layout; Object recognition; Relational databases; Telecommunications;

fLanguage

English

Journal_Title

Fuzzy Systems, IEEE Transactions on

Publisher

ieee

ISSN

1063-6706

Type

jour

DOI

10.1109/91.917123

Filename

917123