A l’initiative du LMAH, Mohamed Didi Biha, Laboratoire de Mathématiques Nicolas Oresme, Université de Caen Normandie, interviendra à l’université Le Havre Normandie pour un séminaire intitulé : “Sous-graphe connexe, couplages et partitions”.
Etant donné un graphe G=(V,E) muni d’une fonction poids W de E dans IR, le problème du sous-graphe connexe maximum (SGCM) consiste à déterminer un sous-ensemble d’arêtes F qui induit un sous graphe connexe et dont le poids est maximum. Nous établissons le lien entre la complexité algorithmique de ce problème et le matching number (cardinalité d’un couplage maximum). Nous présentons une étude sur le problème de séparation associé aux inégalités dites de “Partition-couplage” introduite par D.B, Kerivin et Pei dans le cadre d’une étude polyédrale du problème SGCM.
Le travail présenté a été fait en collaboration avec Hervé Kerivin (LIMOS, Clermont-Ferrand).
