 |
Exploration arborescente et décomposition pour le problème de plus grand graphe partiel commun
1 : Laboratoire de Mathématiques de lÍNSA de Rouen Normandie
Institut national des sciences appliquées Rouen Normandie
2 : Laboratoire de Mathématiques de l'INSA de Rouen (LMI)
Institut National des Sciences Appliquées (INSA) - Rouen, Institut National des Sciences Appliquées [INSA] - Rouen : EA3226
Le problème du plus grand graphe partiel commun a été introduit en premier par Bokhari pour résoudre le problème d'affectation de tâches à des processeurs tout en maximisant les demandes de communications entre tâches. Ce problème donne également une mesure de similarité entre deux graphes et est utilisé comme outil pour comparer des molécules. Nous proposons une approche par exploration arborescente, nous donnons des bornes duales efficaces et explorons des approches pour briser les symétries et décomposer le problème.
