Universitat Politècnica de Catalunya
2009-10-16
B. 15957-2012
376 p.
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
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.
Teoria de grafs; Traffic grooming; Xarxes òptiques; Particions de grafs; Complexitat computacional; Algorismes d'aproximació; Complexitat paramètrica; Grafs en superfícies
51 - Mathematics
ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
