<  Back to the Polytechnique Montréal portal

A Google-inspired error-correcting graph matching algorithm

Segla Kpodjedo, Philippe Galinier and Giuliano Antoniol

Technical Report (2008)

Published Version
Terms of Use: All rights reserved.
Download (711kB)
Cite this document: Kpodjedo, S., Galinier, P. & Antoniol, G. (2008). A Google-inspired error-correcting graph matching algorithm (Technical Report n° EPM-RT-2008-06).
Show abstract Hide abstract


Graphs and graph algorithms are applied in many different areas including civil engineering, telecommunications, bio-informatics and software engineering. While exact graph matching is grounded on a consolidated theory and has well known results, approximate graph matching is still an open research subject. This paper presents an error tolerant approximated graph matching algorithm based on tabu search using the Google-like PageRank algorithm. We report preliminary results obtained on 2 graph data benchmarks. The first one is the TC-15 database [14], a graph data base at the University of Naples, Italy. These graphs are limited to exact matching. The second one is a novel data set of large graphs generated by randomly mutating TC-15 graphs in order to evaluate the performance of our algorithm. Such a mutation approach allows us to gain insight not only about time but also about matching accuracy.

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2713 Algorithmes
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Date Deposited: 03 Jul 2018 15:42
Last Modified: 16 Jun 2021 17:09
PolyPublie URL: https://publications.polymtl.ca/3166/
Document issued by the official publisher
Report number: EPM-RT-2008-06


Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only