Rebonjour, Voici donc l'expose que je souahite presenter a l'Ecole Jeunes Chercheurs. Et encore merci pour l'extension de la deadline... Guillaume. Titre : Routage de 2-1 Requtes dans l'Hypercube RŽsumŽ : On se place dans l'hypercube orientŽ symŽtrique de dimension $n$, $H_n$. On se donne $R$, une 2-1 requte dans $H_n$, c'est-ˆ-dire un ensemble de couples {source,destination} appartenant ˆ $V(H_n)\times V(H_n)$, o chaque sommet de $H_n$ peut tre utilisŽ 2 fois comme source, mais 1 seule fois comme destination. Supposons $n$ fixŽ. Pour une 2-1 requte $R$ donnŽe dans $H_n$, on appelle ``routage'' un ensemble de chemins qui pour chaque couple {source,destination} va du sommet source vers le sommet destination. Si on est capable de trouver, pour chaque 2-1 requte, un routage tel que les arcs utilisŽs par ce routage sont deux ˆ deux distincts, on dit que $H_n$ est ``rŽarrangeable'' vis-ˆ-vis des 2-1 requtes~; de plus, le routage sera dit ``arc-disjoint''. On montre ici que pour tout $n\geq 3$, $H_3$ n'est pas rŽarrangeable vis-ˆ-vis des 2-1 requtes. Pour tout $n\geq 3$, il est en effet possible d'exhiber une 2-1 requte $g_n$, construite rŽcursivement, pour laquelle aucun routage ne peut tre arc-disjoint. Il s'agit d'un travail rŽalisŽ en collaboration avec Olivier Baudon (LaBRI) et Ivan Havel (AcadŽmie des Sciences de la RŽpublique Tchque, Prague). --- Guillaume Fertin LaBRI, UniversitŽ Bordeaux I Bureau 119 351 Cours de la LibŽration TŽl: 05-56-84-69-11 33405 TALENCE Cedex, France http://dept-info.labri.u-bordeaux.fr/~fertin/ mailto:fertin@labri.u-bordeaux.fr ------------ "Excess is not enough"