Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks

Description

The first part of this thesis is devoted to traffic grooming, which is a central problem in optical networks. It refers to packing low-rate signals into higher-speed streams, in order to improve bandwidth utilization and reduce the network cost. The objective is to minimize the number of Add-Drop Multiplexers (ADMs), which are devices that insert/extract low-rate traffic to/from a high-speed stream. In graph-theoretical terms, the problem can be translated into finding a partition of the edges of a request graph into subgraphs with bounded number of edges, the objective being to minimize the total number of vertices of the partition. We first focus in Chapter 1 on a general request graph when the topology is a ring or a path. We provide the first inapproximability result for traffic grooming for fixed values of the grooming factor C, answering affirmatively to a conjecture in the literature. We also provide a polynomial-time approximation algorithm for traffic grooming in rings and paths, with an approximation ratio independent of C. We introduce in Chapter 2 a new model of traffic grooming in unidirectional rings, in order to design networks being able to support any request graph with bounded maximum degree. We show that the problem is essentially equivalent to finding the least integer M(C,D) such that the edges of any graph with maximum degree at most D can be partitioned into subgraphs with at most C edges and each vertex appears in at most M(C,D) subgraphs, and we establish the value of M(C,D) for almost all values of C and D. In Chapter 3 we focus on traffic grooming in bidirectional rings with symmetric shortest path routing and all-to-all unitary requests, providing general lower bounds and infinite families of optimal solutions for C=1,2,3 and C of the form k(k+1)/2. In Chapter 4 we study traffic grooming for two-period optical networks, a variation of the traffic grooming problem for WDM unidirectional ring networks with two grooming factors C and C' that allows some dynamism on the traffic. Using tools of graph decompositions, we determine the minimum number of ADMs for C=4, and C'=1,2,3. The study of the traffic grooming problem leads naturally to the study of a family of graph-theoretical problems dealing with general constraints on the degree. This is the topic of the second part of this thesis. We begin in Chapter5 by studying the computational complexity of several families of degree-constrained problems, giving hardness results and polynomial-time approximation algorithms. We then study in Chapter 6 the parameterized complexity of finding degree-constrained subgraphs, when the parameter is the size of the subgraphs. We prove hardness results in general graphs and provide explicit fixed-parameter tractable algorithms for minor-free graphs. We obtain in Chapter 7 subexponential parameterized and exact algorithms for several families of degree-constrained subgraph problems on planar graphs, using bidimensionality theory combined with novel dynamic programming techniques. Finally, we provide in Chapter 8 a framework for the design of dynamic programming algorithms for surface-embedded graphs with single exponential dependence on branchwidth. Our approach is based on a new type of branch decomposition called surface cut decomposition, which generalizes sphere cut decompositions for planar graphs. The existence of such algorithms is proved using diverse techniques from topological graph theory and analytic combinatorics.

Abstract (French)

La première partie de cette thèse s'intéresse au groupage de trafic dans les réseaux de télécommunications. La notion de groupage de trafic correspond à l'agrégation de flux de faible débit dans des conduits de plus gros débit. Cependant, à chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud, ce qui représente un coût d'équipements important. Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part la réduction du coût des équipements de routage. Nous présentons des résultats d'inapproximabilité, des algorithmes d'approximation, un nouveau modèle qui permet au réseau de pouvoir router n'importe quel graphe de requêtes de degré borné, ainsi que des solutions optimales pour deux scénarios avec trafic all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de manière dynamique. La deuxième partie de la thèse s'intéresse aux problèmes consistant à trouver des sous-graphes avec contraintes sur le degré. Cette classe de problèmes est plus générale que le groupage de trafic, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donné avec contraintes sur le degré, tout en optimisant un paramètre du graphe (très souvent, le nombre de sommets ou d'arêtes). Nous présentons des algorithmes d'approximation, des résultats d'inapproximabilité, des études sur la complexité paramétrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une méthodologie générale qui permet de résoudre efficacement cette classe de problèmes (et de manière plus générale, la classe de problèmes tels qu'une solution peut être codé avec une partition d'un sous-ensemble des sommets) pour les graphes plongés dans une surface. Finalement, plusieurs annexes présentent des résultats sur des problèmes connexes.

Additional details