Browse Prior Art Database

An inexact graph matching technique using Genetic Algorithms

IP.com Disclosure Number: IPCOM000063607D
Original Publication Date: 2005-Feb-18
Included in the Prior Art Database: 2005-Feb-18

Publishing Venue

IBM

Abstract

Graph is a versatile datastructure for representing and processing relational information. Inexact graph matching is the process of determining the best possible match of one graph against another where there is not much correspondence between the graphs. The inexact graph matching problem is NP-hard. This paper proposes a genetic algorithm based technique to find the best possible match between two graphs. The technique is aided by loosely coupled similarity estimation metrics to perform the matching. The technique has been applied to a real world inexact graph matching problem and the results have been provided.