Routage de permutations dans les arbres

Nous étudions un problème de routage de permutations dans les arbres. Nous montrons que ce problème est NP-difficile mais 5/3 approximable. Dans le cas de la chaîne et des étoiles géneralisées, ce problème est polynomial et nous calculons la complexité moyenne. Nous calculons des bornes dans le cas général d'un réseau arborescent. Ceci est un travail en collaboration avec D. Barth, A. Denise, D. Gardy et M. Valencia.