Graphes et équilibres d'orientations

Session : PJC-1 / Prix Jeune Chercheur
Mercredi 10 février 11:00 - 12:40 Salle : Amphi-CI
Antoine Glorieux, Walid Benameur et José Neto

Nous étudions le problème qui consiste à orienter les arêtes d'un graphe de manière à maximiser le minimum sur tout les sommets de la différence en valeur absolue entre le degré sortant et le degré entrant. Ce minimum est appelé le déséquilibre de l'orientation, autrement dit, plus il est grand, plus l'orientation est déséquilibrée. Nous appelons ce Problème NP-complet MaxIm et en présentons des résultats d'approximabilité et inapproximabilité. Ensuite nous introduisons deux formulations de notre problème en programmation linéaire mixte dont une renforcée par un algorithme de plans coupants. Puis nous caractérisons les graphes pour lesquels la valeur optimale de MaxIm est nulle et enfin nous décrivons un algorithme exacte résolvant le problème MaxIm sur les cactus en temps polynomial.

Mots clés : graphes, orientation, complexité, programmation linéaire mixte, (in)-approximabilité, cactus