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.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/78908 |
| Date | 16 October 2009 |
| Creators | Sau Valls, Ignasi |
| Contributors | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | English |
| Detected Language | French |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 376 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, 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. |
Page generated in 0.0024 seconds