Sylvie Corteel, LRI, Orsay

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.


Virginie Collette
Last modified: Thu Jun 8 17:03:13 MET DST 2000