Techniques de Décomposition pour l'Isomorphisme de Sous-Graphe

Résumé : Les techniques existantes de décomposition sont inefficaces sur des problèmes dont le graphe de contraintes initial est complet. Nous nous intéressons en particulier au problème de l'isomorphisme de sous-graphe, et montrons comment utiliser une approche hybride de décomposition statique et dynamique pour ce problème. L'idée sous-jacente est de précalculer une heuristique statique sur un sous-ensemble du réseau de contraintes, de suivre cette heuristique statique, et d'utiliser pour le reste de la recherche une propagation forte ainsi que une détection dynamique de décomposition du réseau de contraintes. Les résultats expérimentaux montrent que pour des graphes à faibles degrés, notre méthode de décomposition résout plus d'instances que les algorithmes dédiés pour l'isomorphisme de sous-graphe et pour les approches par contraintes existantes.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.227-236, 2008
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00291639
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 16:31:37
Dernière modification le : jeudi 10 juillet 2008 - 16:34:26
Document(s) archivé(s) le : vendredi 28 mai 2010 - 19:26:39

Fichier

pages-227-236-article39.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291639, version 1

Collections

Citation

Stéphane Zampelli, Martin Mann, Yves Deville, Rolf Backofen. Techniques de Décomposition pour l'Isomorphisme de Sous-Graphe. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.227-236, 2008. 〈inria-00291639〉

Partager

Métriques

Consultations de la notice

119

Téléchargements de fichiers

107