| Auteur | Boutiche, Mohamed Amine | | Directeur de thèse | Lethi, Hoai An (Professeur) | | Filière | Mathématiques | | Diplôme | Doctorat | | Titre | Techniques de décompositions de graphes appliquées au problème de routage | | Mots clés | Routage (informatique) ; Architecture des réseaux d'ordinateurs ; Graphes, Théorie des ; Graphes, Théorie topologique des | | Résumé | L'objectif de cette thèse est d'une part étudier une nouvelle notion de graphe, "la longueur arborescente des graphes" venue compléter celle largement étudiée, la largeur arborescente. Notre contribution a été le calcul de la longueur arborescente pour des classes de graphes plus larges que celles proposées jusque là, la classe des graphes faiblement triangulés et celle des graphes k – cordaux.
D’autre part, et dans la deuxième partie de notre travail, nous avons considéré que la topologie du réseau est dynamique (i.e.; des modifications sur les liens ou sur les nœuds du réseau surviennent à travers le temps), donc nous avons proposé de maintenir cette topologie à chaque modification. Notre contribution consiste en un algorithme dynamique pour les graphes faiblement triangulés et une généralisation pour les graphes quelconques, et qui supporte les opérations de suppression et d'ajout d'arêtes et de sommets. De plus, nous mettons à jour les paramètres largeur et longueur arborescente quand des changements dans la topologie surviennent.
| | Date de soutenance | 12-12-2013 | | Cote | 511.5 | | Pagination | 77 p. | | Illusatration | ill. | | Format | 30 cm. | | Notes | Support papier accompagné d'un CD-Rom ; Bibliogr. p. 67-77 | | Statut | Traitée |
|