Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Algorithme de Renversement de Liens : convergence et complexité
Bernadette Charron-Bost

18 June 2013, 10:00 - 18 June 2013, 12:00
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :
Les algorithmes de Renversement de Liens (LR) constituent un schéma algorithmique distribué de base en particulier pour les réseaux mobiles ad-hoc. Ce schéma a été proposé à l'origine par Gafni et Bertsekas en 1981 pour le routage et a été par la suite utilisé pour l'élection de leader, l'exclusion mutuelle ou encore l'allocation de ressources. Les deux algorithmes LR les plus populaires sont l'algorithme Full Reversal (FR) et l'algorithme Partial Reversal (PR).

Nous proposons tout d'abord une version unifiée de tous les algorithmes LR et donnons une preuve générale de convergence de ces algorithmes. En particulier, nous donnons la première preuve de convergence de l'algorithme Partial Reversal. A partir de cette version unifiée, nous calculons exactement la complexité en travail de chaque algorithme LR alors que seule la complexité en travail de Full Reversal était connue jusqu'à présent.

Pour la complexité en temps, seules des bornes étaient connues dans le cas de l'algorithme Full Reversal. En montrant que le comportement de l'algorithme Full Reversal correspond en fait à un système dynamique linéaire dès lors que l'on travaille dans l'algèbre min-plus, nous établissons une expression exacte de la complexité en temps de Full Reversal. Une réduction générale au cas Full Reversal permet ensuite de calculer la complexité en temps de chaque algorithme LR.

A l'aide d'outils élémentaires de théorie des jeux, nous menons une étude comparative des différents algorithmes LR. En particulier, nous montrons que vis à vis de la complexité en travail l'algorithme Partial Reversal est meilleur que l'algorithme Full Reversal alors que vis à vis de la complexité en temps, les conclusions sont inverses.

Travail en collaboration avec M. Fuegger (TU, Wien), J. Welch (Texas A&M University) et J. Widder (TU, Wien).

Pour en savoir plus :
Séminaires
Refining Transitive and Pseudo-Transitive Relation
Web data management
Monday 24 January 2022 - 13:00
Salle : 455 - PCRI-N
Shuai Wang .............................................

Discovering Causal Rules in Knowledge Graphs using
Integration of Data and Knowledge
Monday 10 January 2022 - 15:00
Salle : 455 - PCRI-N
Lucas Simonne .............................................

Meta-Learning for Few-Shot Link Prediction in Know
Integration of Data and Knowledge
Monday 13 December 2021 - 13:00
Salle : 455 - PCRI-N
Taha Halal .............................................

Knowledge Graph Refinement based on Triplet BERT-N
Web data management
Monday 29 November 2021 - 13:00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Automated Reasoning
Monday 15 November 2021 - 13:00
Salle : 445 - PCRI-N
Hui Yang .............................................