L(2,1)-labelling of graphs (2008)
Havet, Frederic, Reed, Bruce, Sereni, Jean-Sebastien
An $L(2,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq 2$ if $dist(x,y)=1$ and $|f(x)-f(y)|\geq 1$ if $dist(x,y)=2$, where...
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sebastien
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,...
Characterization of graphs and digraphs with small process number (2008)
Coudert, David, Sereni, Jean-Sebastien
The process number of a digraph has been introduced as a tool to study rerouting issues in WDM networks. We consider the recognition and the characterization of (di)graphs with process number at most...
Improper colouring of unit disk graphs (2007)
Havet, Frederic, Kang, Ross, Sereni, Jean-Sebastien
Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is k -improper if no vertex receives the same colour as k +1 of its...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sebastien
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...
Rerouting requests in WDM networks (2005)
Coudert, David, Perennes, Stephane, Pham, Quang-Cuong, Sereni, Jean-Sebastien
We model a problem related to routing reconfiguration in WDM networks. We establish some similarities and differ- ences with two other known problems: the pathwidth and the pursuit problem. We then...