Date : 2002
Editeur / Publisher : [S.l.] : [s.n.] , 2002
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Structures de données (informatique)
Résumé / Abstract : Dans un réseau de communication, pour diffuser des messages destinés aux membres d'un groupe multipoint, il convient de trouver une façon d'acheminer les messages qui mobilise un minimum de liens de communication et qui s'effectue en un minimum de temps. Cette thèse porte sur la satisfaction simultanée de ces deux contraintes, à priori contradictoires, et ceci dans le cas où la pondération des arêtes employées est la même pour le calcul du temps de traversée et pour le calcul du poids d'un sous-graphe. Après avoir situé notre travail dans son contexte, nous présentons deux théorèmes d'impossibilité ainsi qu'une variante NP-difficile de notre problème. Puis, nous présentons deux algorithmes d'approximation complémentaires, que nous comparons. Ces algorithmes sont paramétrables et permettent de favoriser tantôt le poids ou le délai. Nous nous attaquons ensuite aux aspects incrémentaux de ce problème, condition indispensable à des applications pratiques. Nous commençons par introduire un algorithme d'ajout que nous analysons à l'aide de simulations. Enfin, Nous procédons à une étude théorique du retrait.
Résumé / Abstract : In a communication network, in order to dispatch a message to the members of a multipoint group, one need to find a way of routing the messages that uses the less possible links and that takes a minimum time. This thesis deals with the simultaneous satisfaction of those two contradictory constraints, in the case where the weighting or the edges represents both the delay and the cost. After situating our work in its context, we present two impossibility theorems as well as an NP-hard variant of our problem. Then we present and compare two approximation algorithms. Those algorithms are parameterizable and allow one to favor the cost or the delay. We next deal with incremental aspects of this problem, which is a very important condition to practical applications. We begin by introducing an algorithm for adding new members to the group, that we analyze with simulations. At last, we proceed to a theoretical study of the removal of a member from the group.