Eliminations des solutions symétriques pour l'isomorphisme de sous-graphe - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

Eliminations des solutions symétriques pour l'isomorphisme de sous-graphe

Philippe Vismara

Abstract

La programmation par contrainte fournit aujourd'hui des modèles efficaces pour résoudre les problèmes d'isomorphisme de sous-graphe. Beaucoup de problèmes réels nécessitent l'énumération de toutes les solutions qui ne sont pas équivalentes à une symétrie d'un des graphes traités. Dans cet article nous nous intéressons aux conditions sous lesquelles il est possible d’éliminer ces symétries en utilisant des contraintes lexicographiques. Dans le cas où le nombre de symétries devient trop important, nous proposons une méthode basée sur des contraintes ensemblistes.
No file

Dates and versions

lirmm-00830409 , version 1 (05-06-2013)

Identifiers

  • HAL Id : lirmm-00830409 , version 1

Cite

Philippe Vismara. Eliminations des solutions symétriques pour l'isomorphisme de sous-graphe. 9èmes Journées Francophones de Programmation par Contraintes (JFPC 2013), Jun 2013, Aix-en-Provence, France. pp.343-346. ⟨lirmm-00830409⟩
106 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More