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.
Domaines
Langage de programmation [cs.PL]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...