Quelques problèmes de recouvrement dans les graphes

mercredi 16 mai 2018, 13h45, P 510

Cédric Bentz, Conservatoire National des Arts et Métiers - CNAM

"Dans cette présentation, j’évoquerai quelques résultats représentatifs obtenus sur quatre familles de problèmes de recouvrement dans les graphes : multicoupes (multicoupes multicritères, multicoupes planaires), colorations (généralisations des colorations équitables), arbres et réseaux de Steiner (arbres de Steiner avec capacités sur les arêtes/arcs, réseaux de Steiner avec capacités sur les arêtes/arcs en présence de pannes), ainsi que d-bloqueurs et certaines de leurs variantes (complexité du problème des arêtes les plus vitales dans les couplages bipartis, cas particuliers de graphes bipartis et graphes complets)."