Application of genetic algorithms in graph matching

Martin Krcmar, Atam P. Dhawan

Research output: Contribution to conferencePaperpeer-review

11 Scopus citations


Genetic algorithms (GA) can be exploited for optimal graph matching. Graphs represent powerful method of a pattern formal description. Globally optimal graph matching is a NP-complete problem. Pattern distortions and noise increase an optimal search difficulty which could be tackled using GA. This paper describes results of simple GA applied on a graph matching problem. As a conclusion, the suitable GA for an optimal graph `isomorphism' and `monomorphism' is proposed. Used coding resembles the Travelling Salesman Problem (TSP). Consequently, performance of ordering operators has been tested. In contrast to the TSP, the fitness function depends on chromosome value positioning not ordering. It results in differences between optimal GA configuration for graph matching and for TSP.

Original languageAmerican English
Number of pages5
StatePublished - Dec 1 1994
Externally publishedYes
EventProceedings of the 1994 IEEE International Conference on Neural Networks. Part 1 (of 7) - Orlando, FL, USA
Duration: Jun 27 1994Jun 29 1994


ConferenceProceedings of the 1994 IEEE International Conference on Neural Networks. Part 1 (of 7)
CityOrlando, FL, USA

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Application of genetic algorithms in graph matching'. Together they form a unique fingerprint.

Cite this