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.