Segla Kpodjedo, Philippe Galinier et Giuliano Antoniol
Rapport technique (2008)
Document en libre accès dans PolyPublie et chez l'éditeur officiel |
|
Libre accès au plein texte de ce document Version officielle de l'éditeur Conditions d'utilisation: Tous droits réservés Télécharger (540kB) |
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.
Sujet(s): |
2700 Technologie de l'information > 2700 Technologie de l'information 2700 Technologie de l'information > 2713 Algorithmes |
---|---|
Département: | Département de génie informatique et génie logiciel |
URL de PolyPublie: | https://publications.polymtl.ca/3166/ |
Numéro du rapport: | EPM-RT-2008-06 |
Date du dépôt: | 03 juil. 2018 15:42 |
Dernière modification: | 25 sept. 2024 15:36 |
Citer en APA 7: | Kpodjedo, S., Galinier, P., & Antoniol, G. (2008). A Google-inspired error-correcting graph matching algorithm. (Rapport technique n° EPM-RT-2008-06). https://publications.polymtl.ca/3166/ |
---|---|
Statistiques
Total des téléchargements à partir de PolyPublie
Téléchargements par année
Provenance des téléchargements