 |
Couplage parfait disconnectant pour les graphes bipartis de diamètre 3
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
Etant donné G=(V,E) un graphe connexe, le problème du couplage parfait disconnectant consiste à décider s'il existe un couplage parfait M tel que la suppression des arêtes de M disconnecte G.
Le problème est NP-complet lorsque G est biparti et de diamètre 4. Nous montrons que le problème est polynomial lorsque G est biparti et de diamètre 3.
