Elimination des symétries pour l'appariement de graphes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

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.
Fichier principal
Vignette du fichier
58.pdf (245.38 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00085818 , version 1 (14-07-2006)

Identifiants

  • HAL Id : inria-00085818 , version 1

Citer

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. ⟨inria-00085818⟩

Collections

JFPC06
44 Consultations
169 Téléchargements

Partager

Gmail Facebook X LinkedIn More