 |
Dominant minimum dans les graphes sans griffe de diamètre $d$
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
Après avoir montré que le problème du dominant minimum d'un graphe sans griffe est $NP$-difficile pour les graphes de diamètre fixé $d, d\ge 3$, nous montrons un algorithme polynomial pour les graphes de diamètre deux.
