| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [20 references]
https://hal.inria.fr/inria-00085800
Contributor : Laurent Henocque Connect in order to contact the contributor
Submitted on : Friday, July 14, 2006 - 1:49:38 PM
Last modification on : Tuesday, June 1, 2021 - 2:08:03 PM
Long-term archiving on: : Monday, April 5, 2010 - 9:47:01 PM
Contributor : Laurent Henocque Connect in order to contact the contributor
Submitted on : Friday, July 14, 2006 - 1:49:38 PM
Last modification on : Tuesday, June 1, 2021 - 2:08:03 PM
Long-term archiving on: : Monday, April 5, 2010 - 9:47:01 PM