Offre de th
Forum 'Emplois' - Sujet créé le 2011-04-15 par Sylvain DURAND
Titre : Solutions optimales des problèmes de recouvrement sous contraintes sur le degré des noeuds
Mots clés: théorie de graphes, problèmes de recouvrement, problème de Steiner sous contraintes sur
le degré des noeuds, hiérarchies et arbres de recouvrement
Encadrement, contact : Miklos Molnar (molnar@lirmm.fr), Sylvain Durand (sdurand@lirmm.fr)
Équipe: APR LIRMM tél. : 04.67.41.85.40, 04.67.41.86.57
Plusieurs applications – comme le routage multicast et broadcast dans les réseaux, le routage dans les microcircuits et la conception de réseaux – conduisent à l'étude du recouvrement optimal des sommets ou d'un sous-ensemble de sommets dans un graphe. Souvent, on cherche la solution de coût minimal. Sans aucune contrainte, la solution est un arbre de recouvrement. Pour le recouvrement partiel, le problème est connu comme le problème de Steiner qui est NP-difficile. S'il y a des contraintes à respecter, les problèmes de recouvrement deviennent NP-difficile même dans le cas de la couverture de l'ensemble des sommets du graphe.
Le sujet correspond à l'étude des problèmes de recouvrement (partiel ou non) sous contraintes sur le degré des sommets et de leurs solutions. Les contraintes expriment le fait que chaque sommet du graphe possède une capacité limitée et son degré dans la structure recherchée ne peut pas dépasser une certaine valeur. Ce problème a été intensivement étudié dans la littérature. Pratiquement sans exception, sa solution optimale a été supposée arborescente mais l'arbre de recouvrement n'existe pas toujours. Dans certains cas, le problème de l'absence d'une solution vient paradoxalement du fait que finalement la structure optimale n'est pas toujours un arbre de recouvrement. Il a été récemment démontré qu'en présence des contraintes, il faut chercher des structures qui sont différentes des arbres. La structure optimale de recouvrement correspond à une extension du concept d'arbre que nous appelons hiérarchie. C'est une structure hiérarchique, arborescente dans laquelle on peut répéter/réutiliser les éléments du graphe. Dans certains cas, les hiérarchies permettent de trouver des solutions quand il n'y a pas d'arbre qui correspond aux contraintes. Dans d'autres cas, les hiérarchies peuvent représenter des solutions moins couteuses que les arbres.
Dans la thèse, plusieurs problèmes de recouvrement sous contraintes sur le degré des sommets seront examinés : le recouvrement total du graphe (degree constrained spanning problem) et le recouvrement partiel (degree constrained Steiner problem). Étant donné que l'introduction des hiérarchies change la formulation des problèmes, l'analyse large des nouveaux problèmes est nécessaire. On envisage l'analyse de la complexité des différents cas formulés, la recherche des algorithmes exacts, des algorithmes heuristiques pour les cas NP-difficiles et l'analyse des possibilités des solutions approchées.
Mots clés: théorie de graphes, problèmes de recouvrement, problème de Steiner sous contraintes sur
le degré des noeuds, hiérarchies et arbres de recouvrement
Encadrement, contact : Miklos Molnar (molnar@lirmm.fr), Sylvain Durand (sdurand@lirmm.fr)
Équipe: APR LIRMM tél. : 04.67.41.85.40, 04.67.41.86.57
Plusieurs applications – comme le routage multicast et broadcast dans les réseaux, le routage dans les microcircuits et la conception de réseaux – conduisent à l'étude du recouvrement optimal des sommets ou d'un sous-ensemble de sommets dans un graphe. Souvent, on cherche la solution de coût minimal. Sans aucune contrainte, la solution est un arbre de recouvrement. Pour le recouvrement partiel, le problème est connu comme le problème de Steiner qui est NP-difficile. S'il y a des contraintes à respecter, les problèmes de recouvrement deviennent NP-difficile même dans le cas de la couverture de l'ensemble des sommets du graphe.
Le sujet correspond à l'étude des problèmes de recouvrement (partiel ou non) sous contraintes sur le degré des sommets et de leurs solutions. Les contraintes expriment le fait que chaque sommet du graphe possède une capacité limitée et son degré dans la structure recherchée ne peut pas dépasser une certaine valeur. Ce problème a été intensivement étudié dans la littérature. Pratiquement sans exception, sa solution optimale a été supposée arborescente mais l'arbre de recouvrement n'existe pas toujours. Dans certains cas, le problème de l'absence d'une solution vient paradoxalement du fait que finalement la structure optimale n'est pas toujours un arbre de recouvrement. Il a été récemment démontré qu'en présence des contraintes, il faut chercher des structures qui sont différentes des arbres. La structure optimale de recouvrement correspond à une extension du concept d'arbre que nous appelons hiérarchie. C'est une structure hiérarchique, arborescente dans laquelle on peut répéter/réutiliser les éléments du graphe. Dans certains cas, les hiérarchies permettent de trouver des solutions quand il n'y a pas d'arbre qui correspond aux contraintes. Dans d'autres cas, les hiérarchies peuvent représenter des solutions moins couteuses que les arbres.
Dans la thèse, plusieurs problèmes de recouvrement sous contraintes sur le degré des sommets seront examinés : le recouvrement total du graphe (degree constrained spanning problem) et le recouvrement partiel (degree constrained Steiner problem). Étant donné que l'introduction des hiérarchies change la formulation des problèmes, l'analyse large des nouveaux problèmes est nécessaire. On envisage l'analyse de la complexité des différents cas formulés, la recherche des algorithmes exacts, des algorithmes heuristiques pour les cas NP-difficiles et l'analyse des possibilités des solutions approchées.