$d$-contraction optimale d'arêtes d'un graphe

Session : GR / Graphes
Jeudi 11 février 15:00 - 16:40 Salle : RP13
Christophe Picouleau

Nous nous intéressons au nombre minimum d'arêtes d'un graphe à contracter pour diminuer la valeur d'un paramètre du graphe de d unités.

Mots clés : graphe, contraction d'arêtes, graphe parfait, sous-graphe induit interdit, NP-complet