Elimination des symétries pour l'appariement de graphes

Résumé : L'appariement de graphes est une technique utilisée dans de nombreux domaines et peut être modélisé comme un problème de satisfaction de contraintes. Cette approche par contraintes est concurrentielle avec des algorithmes dédiés. Dans cet article, nous développons des techniques de détection et d'élimination de symétries spécifiques pour l'appariement de graphes. Nous montrons également comment ces symétries peuvent être éliminées. Nous montrons aussi comment les symétries de valeur conditionnelles peuvent être automatiquement détectées et utilisées. Une nouveau type de symétrie est présenté, appelé symétrie locale, et nous indiquons comment ce nouveau type de symétrie peut être calculé et exploité. Enfin, nous évaluons les techniques classiques d'élimination de symétries de variable et de valeurs sur des instances difficiles.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00085818
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 16:18:03
Dernière modification le : vendredi 14 juillet 2006 - 17:41:42
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:10:20

Fichier

Identifiants

  • HAL Id : inria-00085818, version 1

Collections

Citation

Stéphane Zampelli, Yves Deville, Pierre Dupont. Elimination des symétries pour l'appariement de graphes. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085818〉

Partager

Métriques

Consultations de la notice

97

Téléchargements de fichiers

230