|
 
|
APPAS
|
Début:
01-10-2011
Fin:
30-09-2014
Convention:
Region Ile de France
|
Le projet avait pour but l'étude du problème de Steiner dans les graphes orientés, qui consiste à créer une arborescence connectant un sous-ensemble de noeuds. Ce problème a de nombreuses applications dans les réseaux pour modéliser le multi-cast. Cette modélisation par des graphes orientés est nécessaire lorsque l'on introduit des notions de bande passante et de réservations pour la QoS. En effet, le réseau est alors asymétrique, certains liens peuvent ne pas être utilisables dans les deux directions.
Participants
Supélec
Description
Le problème de l'arborescence de Steiner dans les graphes orientés, qui semble a priori être une simple extension du cas non-orienté, est en réalité très différent de ce dernier, et peu de résultats sont connus. Le principal est qu'il n'existe pas d'algorithme d'approximation à rapport constant, au contraire du cas non-orienté. Ceci pose un ensemble de questions ouvertes telles que l'existence d'un algorithme d'approximation, le meilleur rapport d'approximation ou les algorithmes pour des instances particulières.
Les réseaux de communication intègrent des contraintes qui ne sont pas dé finies dans la présentation classique du problème. Nous avons ainsi pris en considération ces contraintes a fin d'enrichir le problème théorique et d'améliorer sa compréhension. Enfi n,
nous avons proposé une bibliothèques d'algorithmes destinés à la résolution du problème de multi-cast dans les réseaux.
Ce projet était un projet DIGITEO DIM (dans la thématique "Réseaux du futur"), auquel participait Cédric Bentz (pour le LRI, puis le CEDRIC après sa mutation en 2012), Marc-Antoine Weisser (pour Supélec) et Dominique Barth (pour le laboratoire PRiSM et l'UVSQ). Il a notamment financé, de 2011 à 2014, la thèse de Dimitri Watel, co-encadré par les trois participants pré-cités.
