 |
Partition de graphe sous contrainte de ratio de degré
1 : Centre d'études et de recherche en informatique et communications
Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise : EA4629, Conservatoire National des Arts et Métiers [CNAM] : EA4629, Ecole Nationale Supérieure d\'Informatique pour l\'Industrie et l\'Entreprise : EA4629
Soit G=(S,A) un graphe connexe simple et non orienté. Etant donné une partition non triviale (S_1,S_2) des sommets de G, la satisfaction d'un sommet s de S_i est le rapport entre la taille de son voisinage fermé dans S_i et la taille de son voisinage fermé dans S. La qualité de cette partition est définie par la plus petite satisfaction d'un sommet du graphe. Nous nous intéressons à la qualité maximum parmi toutes les partitions non triviales possibles des sommets de G.
