moteur de recherche

Séminaire Algo - Cédric Bentz
Séminaire Algo - Cédric Bentz
16-Apr-2019 14:00
Age: 154 days





Cédric Bentz

Complexité (paramétrée ou non) de problèmes d'optimisation dans les graphes

Seminar room 4B125 (Copernic building)

Abstract: Dans cet exposé, je présenterai des résultats récemment obtenus qui concernent des généralisations de problèmes classiques d'optimisation dans les graphes, du point de vue de la complexité classique ou paramétrée.

Je m'intéresserai tout d'abord au problème de la multicoupe minimum, et à certaines de ses généralisations (variantes partielle et partielle généralisée), dans les graphes planaires ou non. Les paramètres considérés seront le nombre de sources/puits, et une certaine largeur arborescente (pas nécessairement celle du graphe support).

Ensuite, j'évoquerai des problèmes d'arbres de Steiner en présence de capacités sur les arêtes. J'insisterai notamment sur les principaux enseignements de l'étude que nous avons menée sur ces problèmes (avec M.-C. Costa et A. Hertz), sur les liens avec d'autres problèmes de graphes bien connus (dont des problèmes de chemins disjoints), et sur quelques cas particuliers remarquables.

Enfin, j'étudierai des problèmes de coloration plus généraux que ceux de la coloration équitable et de la coloration bornée, et notamment dans certaines classes de graphes particulières (comme les graphes scindés).








<- Back to: Accueil