Techniques de Décomposition pour l'Isomorphisme de Sous-Graphe
(2008) Ournées Francophones de Programmation par Contraintes (JFPC′08) — Location: Nantes, France (4.June.2008)
Files
techdecomp.pdf
Open Access - Adobe PDF
- 182.3 KB
Details
- Authors
- Abstract
- Les techniques existantes de décomposition sont in- efficaces 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´e- 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 `a faibles degrés, notre méthode de d´e- 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.
- Affiliations
Albert-Ludwigs-University Freiburg Institute of Computer Science
Citations
Zampelli, S., Mann, M., Deville, Y., & Backofen, R. (2008). Techniques de Décomposition pour l’Isomorphisme de Sous-Graphe. Ournées Francophones de Programmation par Contraintes (JFPC′08), Nantes, France. https://hdl.handle.net/2078.5/253738