Communications

My main concern is to design efficient algorithms for solving problems arising in telecommunication networks. Since most of these problems are NP-hard in general, I try to use structural properties of considered networks to derive polynomial-time exact or approximation algorithms in particular graph classes. One powerful tool I use to determine and to understand the algorithmic interest of graph structures is pursuit-evasion games. In these games, a team of searchers/pursuers/cops aims at capturing a fugitive/evader/robber moving in a graph. Below I briefly describe some works that I have presented in national/international seminars and conferences. (I have been there)

Here are brief overviews on Pursuit-evasion Games and Applications
Cops and Robber Games

Given a graph G, the seminal cops and robber game involves two players [Nowakowski and Winkler, Quilliot, 1983]. Player 1 first places its cops on vertices of G, then Player 2 places its Robber on one node. Then, turn by turn, Player 1 moves its cops to neighboring nodes and then Player 2 does as well with its robber (cops and robber may stay idle). This is a full information game in the sense that cops and robber are always visible to each other. The Cops win if eventually one cop occupies the same node as the robber, and the Robber wins otherwise. The cop-number of a graph G is the smallest number of cops that ensures that the robber will eventually be captured in G. In particular, Meyniel conjectured that O(n1/2) cops are sufficient to capture a robber in any n-node graph (1985).
While still open in general graphs, this conjecture has been proved in many graph classes (bounded genus, graph exclusing fixed minor, etc.). I continued this study of graph properties through various variants of this game.
Graph Searching and Graph Decompositions

In graph searching, a team of searchers aims at capturing a arbitrary fast omniscient fugitive in a graph. The searchers can be placed at or removed from the nodes of a graph (they can jump). The fugitive can move along paths of the graph as long as it does not meet any searcher. The fugitive is captured when a searcher lands at the same node and the fugitive cannot flee. If the fugitive is invisible, the smallest number of searchers required to capture it in a graph G equals the pathwith of G plus 1. If the fugitive is visible, it is its treewidth plus 1. In some (equivalent) variants the searchers also can slide along edges.
I study graph searching as it provides an algorithmic interpretation of graph decompositions. I also study this problem in a distributed setting as it provides a natural way to understand how mobile agents have to colaborate in order to achieve a task in a network.
Routing Reconfiguration in WDM Networks

The configuration of a network (e.g. WDM) corresponds mainly to the routing (and wavelengths assignment) of connection requests of the network. To optimize the usage of resources with the evolution of the traffic matrix, or to avoid using particular resources subject to maintenance operation, it may be necessary to change the configuration of the network. It is then required to first determine the new configuration and then to schedule necessary changes to switch from the current configuration to the new one, while limiting possible traffic perturbations to customers (traffic disruption). The latter problem is called the routing reconfiguration problem. The study of the reconfiguration problem led to the definition of a new variant of graph searching in directed graph, called processing game.
In this game, searchers can (as in classical graph searching) be placed at or removed from vertices of the graph. The difference comes from the way the fugitive is captured: the capture occurs as soon as the fugitive cannot access a strongly connected subgraph without any searcher. In particular, it means that capturing the fugitive does not require to visit all vertices. For instance, in symmetric digraph, the fugitive is captured if it is surrounded by searchers.
Distributed Routing

Routing tables are a zone of local information available in each node of a network. When a message arrives at some node v, it chooses what is its next hop accoring to its destination and the content of the routing table of v. For instance, when you arrive in some city, the next road you will follow depends on your destination and on the road signs that you see. The performance measures are the size of the routing tables and the length of the routes.
Current telecommunication networks are subject to huge dynamicity (topology, traffic). Therefore, new paradigms of routing must be proposed to handle this dynamicity (e.g., update routing tables). In particular, structural properties must be considered.
Graph Optimization

Mainly on graph properties and/or distributed/centralized algorithms to compute them.
Popularization