COUDERT , David

No description

The general contexts of my research activity are the connection oriented networks, either WDM (wavelength division multiplexing) optical network, or MPLS (Multi-protocol label switching), or wireless backhaul networks using microwave links. In such networks, I am interested in routing data flows, in aggregating low rate traffic streams into...

This thesis deals with optical communication networks, especially free space optical networks and optical fiber networks.First we address the design of free space optical networks using the Optical Transpose Interconnection System (OTIS) architecture defined in [MMHE93]. We give a model of these networks with H(p,q,d) digraphs which we...

In this paper, we present a new set of constraints for modeling linear ordering problems on graphs using Integer Linear Programming (ILP). These constraints express the membership of a vertex to a prefix rather than the exact position of a vertex in the ordering. We use these constraints to propose new ILP formulations for well-known linear...

Cette étude s'intèresse à la planification de réseaux de télécommunications tolérants aux pannes. Nous cherchons à établir, pour chaque couple de noeuds du réseau, deux chemins de communication disjoints, l'un étant réservé à la protection de l'autre. Pour un réseau à n noeuds et m liens de communications, nous donnons un algorithme en O(n(m+n...

The routing reconfiguration problem in WDM networks is to schedule the switching's of a set of lightpaths from one routing to a new predetermined one. This problem is modeled as a digraph processing game, closely related to graph searching games, in which a team of agents is aiming at clearing, or processing, the vertices of a digraph. In this...

We answer open questions of [Verbeek and Suri, SOCG'14] on the relationships between Gromov hyperbolicity and the optimal stretch of graph embeddings in Hyperbolic space. Then, based on the relationships between hyperbolicity and Cops and Robber games, we turn necessary conditions for a graph to be Cop-win into sufficient conditions for a graph...

Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and...

Dans un graphe, existe-t-il un circuit visitant chaque sommet une fois et une seule ? Une question difficile pour certains graphes...Cet article explique comment les auteurs ont abordé et remporté la compétition internationale organisée par la Flinders University d'Adelaïde (Australie), intitulée FHCP Challenge, sur le problème du cycle...

We consider the problem of finding a lightpath assignment for a given set of communication requests on a multifiber WDM optical network with wavelength translators. Given such a network, and w the number of wavelengths available on each fiber, k the number of fiber per link and c the number of partial wavelength translation available on each...

This paper has a double purpose. In the first part of the paper we give an overview of different aspects of graph theory which can be applied in communication engineering, not trying to present immediate results to be applied neither a complete survey of results, but to give a flavor of how graph theory can help research in optical networks....

Nous démontrons l'influence de propriétés des réseaux d'interconnexion de centres de données sur l'étirement obtenu pour des routages dits "géométriques". Ces routages reposent sur un plongement des sommets du graphe dans un espace métrique "simple" tel que le plan Hyperbolique. Les réseaux d'interconnexions des centres de données sont...

Topologies for data center interconnection networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes...

Nous considérons le problème du routage optique d'un ensemble donné de requêtes de communications dans un réseau WDM multifibres avec conversion partielle. Étant donné un tel réseau disposant de w longueurs d'onde par fibre, k fibres par lien et c conversions possibles par nœud du réseau, le problème revient à décider s'il est possible de...

We give an overview of different aspects of graph theory which can be applied in communication engineering, not trying to present immediate results to be applied neither a complete survey of results, but to give a flavor of how graph theory can help this field. We deal in this paper with network topologies, resource competition, state...

Hyperbolicity is a measure of the tree-likeness of a graph from a metric perspective. Recently , it has been used to classify complex networks depending on their underlying geometry. Motivated by a better understanding of the structure of graphs with bounded hyperbolicity, we here investigate on the hyperbolicity of bipartite graphs. More...

The shortest-path metric d of a connected graph G is 1/2-hyperbolic if, and only if, it satisfies d(u,v) + d(x,y) ≤ max{d(u,x) + d(v,y),d(u,y) + d(v,x)} + 1, for every 4-tuple u,x,v,y of G. We show that the problem of deciding whether an unweighted graph is 1/2-hyperbolic is subcubic equivalent to the problem of determining whether there is a...

We study the complexity of decomposing a graph by means of clique separators. This common algorithmic tool, first introduced by Tarjan, allows to cut a graph into smaller pieces, and so, it can be applied to preprocess the graph in the computation of optimization problems. However, the best-known algorithms for computing a decomposition have...

The process number is the 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 pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this...

The International Symposium on Experimental Algorithms (SEA) is an international forum for researchers in the area of the design, analysis, and experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications (telecommunications, transport, bioinformatics, cryptography,...

The decomposition of graphs by clique-minimal separators is a common algorithmic tool, first introduced by Tarjan. Since it allows to cut a graph into smaller pieces, it can be applied to pre-process the graphs in the computation of many optimization problems. However, the best known clique-decomposition algorithms have respective O(nm)-time...

The shortest-path metric $d$ of a connected graph $G$ is $\frac{1}{2}$-hyperbolic if, and only if, it satisfies $d(u,v) + d(x,y) \leq \max \{ d(u,x) + d(v,y), d(u,y) + d(v,x) \} + 1$, for every $4$-tuple $u,x,v,y$ of $G$. We show that the problem of deciding whether an unweighted graph is $\frac{1}{2}$-hyperbolic is subcubic equivalent to the...

We consider the problem of finding a lightpath assignment for a given set of communication requests on a multifiber WDM optical network with wavelength translators. Given such a network and w, the number of wavelengths available on each fiber, k, the number of fibers per link, and c, the number of partial wavelength translations available on...