Project : mascotte

Section: New Results

Fault tolerance

Protection in WDM networks.

We address here the fault tolerance problems, i.e. the network has to be able to handle the traffic when a fault of a node or a link appears. We consider that in this case the rerouting of the impacted flows has to be done from end to end.

One specific problem is the one of wdm-network protection with subnetworks, particularly loop ones [19]. The advantage is that a loop (cycle) is secured by its reverse loop. If the request graph is represented by a logical graph I , the general problem can be turned into finding a covering of the edges of I by some sub-graphs $I_k$ , such that, for each $I_k$ , there exists in the physical graph G a disjoint routing of the edges of $I_k$ . The goal is to minimize the cost of the equipments ; this last one is a complex parameter ; in some cases it is equivalent to minimize the number of $I_k$ graphs in the covering ; in some other cases one needs to minimizing the induced load. We have completely solved this problem in the case where the graph I is the complete graph (which corresponds to an all-to-all instance) and when the sub-graphs $I_k$ are loops (cycles) and the graph G itself is a cycle. The optimal result uses loops of length 3 or 4. We have also solved the case where only cycles of length 4 are desired in the covering. Finally, we have recently solved the case when the physical graph G is a torus.

Connectivity and Reliability.

In [42] we proved the minimum number of edges that a graph of given order and diameter must have if it is to 2-connected. We also proved a similar bound for 2-edge connected graph. This answered a conjecture from Bollobás.

In [35], we investigate the problem of finding a minimum cost k -connected spanning subgraph in a complete and weighted graph (also referred to as the Survivable Network Design problem). We prove the first explicit lower bound on the approximability of this problem. On the other hand, we design an effective approximation algorithm if the input graph satisfies the sharpened $\beta$ -triangle inequality. Furthermore, we present an efficient approximation algorithm for the augmentation version of the problem in which a minimum-cost set of edges to a given graph G has to be found, satisfying given edge- or vertex-connectivity requirements (also referred to as the Network Augmentation problem).

Coalitions and Distributed Computing.

In [15], we consider the question of the influence of a coalition of vertices, seeking to gain control in local neighborhoods in a general graph. This problem is motivated by fault tolerance and recovery applications in distributed computing, where decisions are taken after a voting process using a majority rule. Say that a vertex v is controlled by the coalition M if the majority of its neighbors are from M . We ask how many vertices (as a function of $\left|M\right|$ ) can M control in this fashion. Upper and lower bounds are provided for this problem, as well as for cases where the majority is computed over larger neighborhoods (either neighborhoods of some fixed radius $r\ge 1$ , or all neighborhoods of radii up to r ). In particular, we look also at the case where the coalition must control all vertices (including or excluding its own), and derive bounds for its size.