Skip to Main content Skip to Navigation
Conference papers

Comparaison de l'optimisation par colonies de fourmis et d'une recherche réactive sur des problèmes d'appariement de graphes

Résumé : De nombreuses applications nécessitent de mesurer la similarité d'objets. Lorsque ces objets sont représentés par des graphes, la mesure de similarité se ramène à un problème d'appariement de graphes, i.e., à la recherche d'une meilleure mise en correspondance des sommets de deux graphes. Dans cet article, nous nous intéressons au calcul d'une similarité de graphes basée sur des appariements multivoques des sommets des graphes. Cette mesure a été montrée générique dans le sens où les autres mesures classiques de similarité de graphes peuvent être vues comme un cas particulier de celle-ci. Nous proposons deux algorithmes de calcul de cette similarité : un algorithme basé sur l'optimisation par colonies de fourmis et un algorithme de recherche locale taboue réactive. Nous comparons l'efficacité de ces deux algorithmes sur deux classes de problèmes d'appariements de graphes difficiles et nous montrons que ces algorithmes obtiennent des résultats complémentaires.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085800
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 1:49:38 PM
Last modification on : Thursday, November 21, 2019 - 2:30:44 AM
Document(s) archivé(s) le : Monday, April 5, 2010 - 9:47:01 PM

File

Identifiers

  • HAL Id : inria-00085800, version 1

Citation

Sébastien Sorlin, Olfa Sammoud, Christine Solnon, Khaled Ghédira. Comparaison de l'optimisation par colonies de fourmis et d'une recherche réactive sur des problèmes d'appariement de graphes. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085800⟩

Share

Metrics

Record views

292

Files downloads

788