moteur de recherche

Séminaire Algo - Hélène Langlois
Séminaire Algo - Hélène Langlois
23-Mar-2021 14:00
Age: 84 days





Hélène Langlois

Quasi-noyaux dans les graphes orientés

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

Abstract : La notion de noyau fut introduite en 1944 par von Neumann et Morgenstern pour l'étude des stratégies gagnantes dans les jeux combinatoires et possède désormais de nombreuses autres applications. Tous les graphes ne possèdent pas de noyau, et même décider si un graphe en possède un est NP-complet. Chvátal et Lovász ont montré en 1974 qu'une petite modification de la définition de noyau assure son existence systématique : tout graphe orienté possède un quasi-noyau. Leur preuve fournit d'ailleurs un algorithme polynomial pour en trouver un dans tout graphe orienté.

Dans cet exposé nous nous intéresserons à la recherche de "petits" quasi-noyaux, motivée par une conjecture d'Erdős et Székely de 1976. Ceci nous amènera à étudier la complexité de trouver un quasi-noyau minimal dans différentes classes de graphes ou encore celle de trouver 3 quasi-noyaux disjoints.








<- Back to: Accueil