HUC , Florian

This thesis deals with different aspects of the conception of telecommunication networks. Such networks are a patchwork of various technologies : antenas-satelite links, radio links and optical links, but also onboard networks of satellites. The problematics differ according to the part of the networks on which we focus, to the type of request...

In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to...

The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(\ell,k)$-routing problem, each node can send at most $\ell$ packets and receive at most $k$ packets. Permutation routing is the particular case...

The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the node search number, and thus to the pathwidth, however they are not always equal. In general determining these parameters...

In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to...

Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by Coudert, Huc and Sereni in [4]). By the results of Boedlander and Fomin [2] this holds for every outerplanar graph and actually is tight by Coudert,...

Nous présentons un algorithme distribué simple calculant le process number des arbres en n étapes, avec un nombre total d'opérations en O(nlog(n)) et un total de O(nlog(n)) bits échangés. De plus cet algorithme est facilement adaptable pour calculer d'autre paramètres sur l'arbre, dont le node search number.

We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis \emph{et al.}~[EST94]. It can be executed in an asynchronous environment, requires an overall computation time of $O(n\log{n})$, and $n$ messages of $\log_3{n}+4$ bits each. The main contribution of...

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant...

In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves the proportion given by the weights associated to each edge. If such colouring exists, we want to find one using a minimum number of colours. We...

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a...

A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber colourings} of labelled digraph which are colourings of the arcs of $D$ such that at each vertex $v$, for each colour in $\lambda$,...

In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More...

A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber colourings} of labelled digraph which are colourings of the arcs of $D$ such that at each vertex $v$, for each colour $\lambda$,...

Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et de $p$ sorties il existe $p$ chemins aretes disjoints reliant les entrees aux sorties. Dans le cas particulier $\lambda = 0$, un reseau $\plk$ est...

The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs...

The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs...

In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We consider a distributed and local algorithm that transmits packets hop by hop in the network and study its behavior. At each step, a node transmits its queued packets to its neighbors in order to optimize a...

In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits packets hop by hop in the network and study its behaviour. At each step, a node transmits its queued packets to its neighbours in order to optimize a...

We study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. This problem is motivated by a frequency allocation problem. We propose approximation algorithms to compute such colouring.

We study a weighted improper colouring problem motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most k (the case k = 0 corresponds to a proper coloring). The objective is...

Motivés par un problème d'allocation de fréquences, nous étudions la coloration impropre des graphes pondérés et plus particulièrement des graphes hexagonaux pondérés. Nous donnons des algorithmes d'approximation pour trouver de telles colorations.

This paper deals with the design of on board networks in satellites (also called Traveling wave tube Amplifiers (TWTA)). These networks should connect signals arriving on some ports of the satellite to amplifiers, even in case of failures of some amplifiers. They are made of links and expensive switches each with 4 links. So, the aim is to...

In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context, requests are routed greedily using available resources without changing the routing of pre-established connections. However, such a policy leads to a...

In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context, requests are routed greedily using available resources without changing the routing of pre-established connections. However, such a policy leads to a...