Yann Hendel
Saint John - Newfounland University

Dans cet exposé, nous nous intéressons à un problème de décomposition de
flot en chemins. Etant donné un graphe pondéré orienté sans cycle et une
fonction de flot, on cherche une décomposition de ce flot en chemins telle
que le chemin le plus long de cette décomposition soit le plus court
possible. Dans un premier temps on étudie la complexité de ce problème:
nous montrons qu'il est possible que ce problème ne soit pas dans NP.
Cependant, si on impose que la valeur du flot ou les coûts des arêtes sont
bornés en la taille d'entrée du problème, alors nous proposons des
certificats qui assurent la présence dans NP de ces sous problèmes. Ces
problèmes sont NP-difficiles au sens fort sauf si la valeur du flot est
borné par une constante auquel cas, il est NP-difficile au sens faible. On
peut alors voir ce problème comme une généralisation du problème à
machines parallèles où l'on cherche à minimiser le temps de fin de
l'ordonnancement. Pour le cas ou la valeur du flot est de deux unités, on
montre que le problème est équivalent à P2||Cmax. Pour une valeur de flot
supérieure, on propose un algorithme pseudopolynomial basé sur la
programmation dynamique, ainsi qu'un schéma d'approximation complètement
polynomial.