<  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)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Published Version
Terms of Use: All rights reserved
Download (540kB)
Show abstract
Hide abstract

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.

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2713 Algorithms
Department: Department of Computer Engineering and Software Engineering
PolyPublie URL: https://publications.polymtl.ca/3166/
Report number: EPM-RT-2008-06
Date Deposited: 03 Jul 2018 15:42
Last Modified: 11 Apr 2024 17:39
Cite in APA 7: Kpodjedo, S., Galinier, P., & Antoniol, G. (2008). A Google-inspired error-correcting graph matching algorithm. (Technical Report n° EPM-RT-2008-06). https://publications.polymtl.ca/3166/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item