Evènement pour le groupe Algorithmique Distribuée


Date 2017-06-13  14:00-15:00
TitreOrientation de graphes dans un environnement asynchrone et avec pannes 
RésuméDans cette présentation, nous nous intéressons à l'orientation de graphe de manière distribuée. Plus précisément, nous cherchons à calculer une orientation minimum, c'est-à-dire à minimiser le degré sortant maximum d'un nœud du graphe. Ce problème d'orientation est notamment une modélisation naturelle pour des problèmes d'allocation de ressources. Nous présentons l'algorithme AvgDegAsync qui fonctionne dans un environnement distribué où les communications sont asynchrones et où les nœuds peuvent être en panne. Notre algorithme garantit une $2(2+epsilon)$-approximation de l'orientation optimale en utilisant un nombre logarithmique de rondes asynchrones. De plus, il ne nécessite pas de connaissance sur le graphe comme le nombre de nœuds ou encore sa densité. Ce travail a été réalisé avec Nicolas Hanusse et une présentation a été donnée à AlgoTel 2017  
Lieu178 
OrateurNoël Gillet 



Aucun document lié à cet événement.

Retour
Retour à l'index