Spelling suggestions: "subject:"algorismes d'aproximación"" "subject:"algorismes d'aproximaciones""
1 |
Optimization in graphs under degree constraints. application to telecommunication networksSau Valls, Ignasi 16 October 2009 (has links)
La premi ere partie de cette th ese s'int eresse au groupage de tra c dans les
r eseaux de t el ecommunications. La notion de groupage de tra c correspond a l'agr egation
de
ux de faible d ebit dans des conduits de plus gros d ebit. Cependant, a chaque insertion
ou extraction de tra c sur une longueur d'onde il faut placer dans le noeud du r eseau un
multiplexeur a insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur
d'onde utilis ee dans le noeud, ce qui repr esente un co^ut d' equipements important. Les objectifs
du groupage de tra c sont d'une part le partage e cace de la bande passante et
d'autre part la r eduction du co^ut des equipements de routage. Nous pr esentons des r esultats
d'inapproximabilit e, des algorithmes d'approximation, un nouveau mod ele qui permet
au r eseau de pouvoir router n'importe quel graphe de requ^etes de degr e born e, ainsi que
des solutions optimales pour deux sc enarios avec tra c all-to-all: l'anneau bidirectionnel
et l'anneau unidirectionnel avec un facteur de groupage qui change de mani ere dynamique.
La deuxi eme partie de la th ese s'interesse aux probl emes consistant a trouver des sousgraphes
avec contraintes sur le degr e. Cette classe de probl emes est plus g en erale que
le groupage de tra c, qui est un cas particulier. Il s'agit de trouver des sous-graphes
d'un graphe donn e avec contraintes sur le degr e, tout en optimisant un param etre du
graphe (tr es souvent, le nombre de sommets ou d'ar^etes). Nous pr esentons des algorithmes
d'approximation, des resultats d'inapproximabilit e, des etudes sur la complexit e
param etrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une m ethodologie
g en erale qui permet de r esoudre e cacement cette classe de probl emes (et de mani ere
plus g en erale, la classe de probl emes tels qu'une solution peut ^etre cod e avec une partition
d'un sous-ensemble des sommets) pour les graphes plong es dans une surface.
Finalement, plurieurs annexes pr esentent des r esultats sur des probl emes connexes.
|
Page generated in 0.0522 seconds