ULHN - UNIVERSITÉ LE HAVRE NORMANDIE

Accueil > Actualités > Recherche > Séminaire - Sous-graphe connexe, couplages et partitions

Séminaire - Sous-graphe connexe, couplages et partitions

jeudi 22 mars 2018 à 15:00

Manifestation scientifique ouverte au grand public

Université Le Havre Normandie, UFR Sciences et Techniques, Salle de séminaire de l'aile G

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).

Mise en ligne : 15-03-2018 - Mise à jour : 21-03-2018

Informations pratiques

LMAH - Laboratoire de Mathématiques Appliquées du Havre - EA 3821

Tél. : 02 32 74 43 46
lmah@univ-lehavre.fr

Actualités

Facebook
Plan du site - Mentions légales – © 2014-2018 Université du Havre - 25 rue Philippe Lebon - BP 1123 - 76063 Le Havre Cedex France
téléphone : +33 (0)2 32 74 40 00 communication@univ-lehavre.fr