
JC. Bermond,
F. Ergincan,
and M. Syska.
Quisquater Festschrift,
volume 6805 of Lecture Notes in Computer Science,
chapter Line Directed Hypergraphs,
pages 2534.
SpringerVerlag,
Berlin Heidelberg,
2011.
[PDF
]
Abstract: 
In this article we generalize the concept of line digraphs to line
dihypergraphs. We give some general properties in particular
concerning connectivity parameters of dihypergraphs and their line
dihypergraphs, like the fact that the arc connectivity of a
line dihypergraph is greater than or equal to that of the original
dihypergraph. Then we show that the De Bruijn and Kautz dihypergraphs
(which are among the best known bus networks) are iterated line
digraphs. Finally we give short proofs that they are
highly connected. 
@inBook{BES11,
author= {JC. Bermond and F. Ergincan and M. Syska},
chapter = { Line Directed Hypergraphs},
title={ Quisquater Festschrift},
publisher= { SpringerVerlag },
address={Berlin Heidelberg},
series= {Lecture Notes in Computer Science},
editor={D. Naccache},
volume={6805},
pages={2534},
year = {2011},
PDF={ftp://ftpsop.inria.fr/mascotte/personnel/JeanClaude.Bermond/PUBLIS/BES11.pdf},
abstract={In this article we generalize the concept of line digraphs to line
dihypergraphs. We give some general properties in particular
concerning connectivity parameters of dihypergraphs and their line
dihypergraphs, like the fact that the arc connectivity of a
line dihypergraph is greater than or equal to that of the original
dihypergraph. Then we show that the De Bruijn and Kautz dihypergraphs
(which are among the best known bus networks) are iterated line
digraphs. Finally we give short proofs that they are
highly connected.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "book",
xpays = {CA},
}

G. A. Wainer,
K. AlZoubi,
O. Dalle,
R.C. Hill,
S. Mittal,
J. L. R. Martin,
H. Sarjoughian,
L. Touraille,
M. K. Traoré,
and B. P. Zeigler.
DiscreteEvent Modeling and Simulation: Theory and Applications,
chapter 18  Standardizing DEVS Simulation Middleware,
pages 459494.
Taylor and Francis,
2011.
[WWW
]
@inbook{WAD+11a,
chapter = {18  Standardizing DEVS Simulation Middleware},
title = {DiscreteEvent Modeling and Simulation: Theory and Applications},
publisher = {Taylor and Francis},
year = {2011},
pages = {459494},
editor = {G. Wainer and P. Mosterman},
author = {G. A. Wainer and K. AlZoubi and O. Dalle and R.C. Hill and S. Mittal and J. L. R. Mart\`in and H. Sarjoughian and L. Touraille and M. K. Traor\'e and B. P. Zeigler},
category = {Multi Modeling and Modeling Formalisms},
url = {http://celldevs.sce.carleton.ca/publications/2010/WADHMMSTTZ10},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "livreschap",
}

G . Wainer,
K. AlZoubi,
O. Dalle,
R. C. Hill,
S. Mittal,
J. L. R. Martin,
H. Sarjoughian,
L. Touraille,
M. K. Traoré,
and B. P. Zeigler.
DiscreteEvent Modeling and Simulation: Theory and Applications,
chapter 17  Standardizing DEVS model representation,
pages 427458.
Taylor and Francis,
2011.
[WWW
]
@inbook{WAD+11b,
chapter = {17  Standardizing DEVS model representation},
title = {DiscreteEvent Modeling and Simulation: Theory and Applications},
publisher = {Taylor and Francis},
year = {2011},
pages = {427458},
editor = {Wainer, G. and Mosterman, P.},
author = {G . Wainer and K. AlZoubi and O. Dalle and R. C. Hill and S. Mittal and J. L. R. Mart\`in and H. Sarjoughian and L. Touraille and M. K. Traor\'e and B. P. Zeigler},
url = {http://celldevs.sce.carleton.ca/publications/2010/WADHMMSTTZ10},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "livreschap",
}

V. Andova,
N. Cohen,
and R. Skrekovski.
Graph Classes (Dis)satisfying the Zagreb Indices Inequality.
MATCH Commun. Math. Comput. Chem.,
65(3):647658,
2011.
[PDF
]
Abstract: 
Recently Hansen and Vuki\^cevi\'c proved that the
inequality $M_1/n \leq M_2/m$, where $M_1$ and $M_2$ are the first and
second Zagreb indices, holds for chemical graphs, and Vuki\^cevi\'c
and Graovac proved that this also holds for trees. In both works is
given a distinct counterexample for which this inequality is false in
general. Here, we present some classes of graphs with prescribed
degrees, that satisfy $M_1/n \leq M_2/m$: Namely every graph $G$ whose
degrees of vertices are in the interval $[c; c + \sqrt c]$ for some integer $c$ satisies this inequality. In addition, we prove that for
any $\Delta \geq 5$, there is an infinite family of graphs of maximum
degree $\Delta$ such that the inequality is false. Moreover, an
alternative and slightly shorter proof for trees is presented, as
well as for unicyclic graphs. 
@article{ACS11,
author = {V. Andova and N. Cohen and R. {\v{S}}krekovski},
title = {Graph Classes (Dis)satisfying the Zagreb Indices Inequality},
journal = {MATCH Commun. Math. Comput. Chem.},
year = {2011},
volume = {65},
number = {3},
pages = {647658},
abstract = {Recently Hansen and Vuki\^cevi\'c proved that the
inequality $M_1/n \leq M_2/m$, where $M_1$ and $M_2$ are the first and
second Zagreb indices, holds for chemical graphs, and Vuki\^cevi\'c
and Graovac proved that this also holds for trees. In both works is
given a distinct counterexample for which this inequality is false in
general. Here, we present some classes of graphs with prescribed
degrees, that satisfy $M_1/n \leq M_2/m$: Namely every graph $G$ whose
degrees of vertices are in the interval $[c; c + \sqrt c]$ for some integer $c$ satisies this inequality. In addition, we prove that for
any $\Delta \geq 5$, there is an infinite family of graphs of maximum
degree $\Delta$ such that the inequality is false. Moreover, an
alternative and slightly shorter proof for trees is presented, as
well as for unicyclic graphs.},
pdf = {http://www.imfm.si/preprinti/PDF/01108.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {FR, SI, MK},
sorte = "revint",
}

M. Basavaraju,
L. S. Chandran,
N. Cohen,
F. Havet,
and T. Müller.
Acyclic edgecoloring of planar graphs.
SIAM Journal of Discrete Mathematics,
25(2):463478,
2011.
[PDF
]
Abstract: 
A proper edgecoloring with the property that every cycle contains edges of
at least three distinct colors is called an {\it acyclic
edgecoloring}. The {\it acyclic chromatic index} of a graph $G$,
denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it
acyclic edgecoloring} with $k$ colors.
We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$.
We settle this conjecture for planar graphs with girth at least $5$.
We also show that $\chi'_a(G)\leq \Delta(G) + 12$ for all planar $G$, which improves a previous result by Fiedorowicz et al. 
@article{BCC+11b,
author = {M. Basavaraju and L. S. Chandran and N. Cohen and F. Havet and T. M\"uller},
title = {Acyclic edgecoloring of planar graphs },
journal = {SIAM Journal of Discrete Mathematics},
volume = {25},
number = {2},
year = {2011},
pages = {463478},
abstract = {A proper edgecoloring with the property that every cycle contains edges of
at least three distinct colors is called an {\it acyclic
edgecoloring}. The {\it acyclic chromatic index} of a graph $G$,
denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it
acyclic edgecoloring} with $k$ colors.
We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$.
We settle this conjecture for planar graphs with girth at least $5$.
We also show that $\chi'_a(G)\leq \Delta(G) + 12$ for all planar $G$, which improves a previous result by Fiedorowicz et al.},
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/BCC+11.pdf},
xeditorialboard = {yes},
xproceedings = {no},
xinternationalaudience = {yes},
xpays = {IN},
}

J. Beauquier,
J. Burman,
and S. Kutten.
A selfstabilizing Transformer for Population Protocols with Covering.
Theoretical Computer Science,
412(33):42474259,
2011.
[WWW
]
Abstract: 
Developing \emph{selfstabilizing} solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design selfstabilizing algorithms. In this paper, we propose an \emph{automatic transformer} for algorithms in an extended \emph{population protocol model}. Population protocols is a model that was introduced recently for networks with a large number of resourcelimited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication ``speed'', which is reflected by their \emph{cover times}. Second, we assume the existence of a special agent with an unbounded memory, the \emph{base station}. The automatic transformer takes as an input an algorithm solving a \emph{static problem} (and meeting some additional
rather natural requirements) and outputs a selfstabilizing algorithm for the same problem. The transformer is built using a \emph{reexecution approach} (the technique consisting of executing an algorithm repeatedly in order to obtain its selfstabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent. 
@article{BBK11,
author = {Beauquier, J. and Burman, J. and Kutten, S.},
title = {A selfstabilizing Transformer for Population Protocols with Covering},
journal = {Theoretical Computer Science},
volume = {412},
number = {33},
year = {2011},
pages = {42474259},
abstract = {Developing \emph{selfstabilizing} solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design selfstabilizing algorithms. In this paper, we propose an \emph{automatic transformer} for algorithms in an extended \emph{population protocol model}. Population protocols is a model that was introduced recently for networks with a large number of resourcelimited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication ``speed'', which is reflected by their \emph{cover times}. Second, we assume the existence of a special agent with an unbounded memory, the \emph{base station}. The automatic transformer takes as an input an algorithm solving a \emph{static problem} (and meeting some additional
rather natural requirements) and outputs a selfstabilizing algorithm for the same problem. The transformer is built using a \emph{reexecution approach} (the technique consisting of executing an algorithm repeatedly in order to obtain its selfstabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.},
url = {http://dx.doi.org/10.1016/j.tcs.2010.09.016},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {IL},
sorte = "revint",
}

J.C. Bermond,
Y. M. Chee,
N. Cohen,
and X. Zhang.
The $\alpha$Arboricity of Complete Uniform Hypergraphs.
SIAM Journal on Discrete Mathematics,
25(2):600610,
2011.
[PDF
]
Abstract: 
The $\alpha$arboricity of the complete 3uniform
hypergraph is determined completely.$\alpha$Acyclicity is an important notion in database theory. The $\alpha$arboricity
of a hypergraph H is the minimum number of $\alpha$acyclic hypergraphs that
partition the edge set of H. 
@article{BCC+11a,
author = {J.C. Bermond and Y. M. Chee and N. Cohen and X. Zhang},
title = {The $\alpha$Arboricity of Complete Uniform Hypergraphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2011},
volume = {25},
number = {2},
pages = {600610},
PDF={ftp://ftpsop.inria.fr/mascotte/Publications/BCCZ11.pdf},
abstract = {The $\alpha$arboricity of the complete 3uniform
hypergraph is determined completely.$\alpha$Acyclicity is an important notion in database theory. The $\alpha$arboricity
of a hypergraph H is the minimum number of $\alpha$acyclic hypergraphs that
partition the edge set of H.},
xeditorialboard={yes},
xinternationalaudience={yes},
xproceedings={no},
xpays = {SG},
sorte = "revint",
}

JC. Bermond,
X. Muñoz,
and I. Sau.
Traffic Grooming in Bidirectional WDM Ring Networks.
Networks,
58(1):2035,
2011.
[WWW
] [PDF
]
Abstract: 
We study the minimization of ADMs (AddDrop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and alltoall unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We first study exhaustively the cases $C=1$, $C = 2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the case $C>3$, focusing specifically on the case $C = k(k+1)/2$ for some $k \geq 1$. We give optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings. 
@Article{BMS11,
author = {JC. Bermond and X. Mu{\~n}oz and I. Sau},
title = {{Traffic Grooming in Bidirectional WDM Ring Networks}},
JOURNAL = {Networks},
year = {2011},
volume = {58},
number = {1},
pages = {2035},
xpays = {ES},
sorte = "revint",
url = {http://dx.doi.org/10.1002/net.20410},
pdf = {http://hal.inria.fr/docs/00/42/91/55/PDF/RR7080.pdf},
abstract = {We study the minimization of ADMs (AddDrop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and alltoall unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We first study exhaustively the cases $C=1$, $C = 2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the case $C>3$, focusing specifically on the case $C = k(k+1)/2$ for some $k \geq 1$. We give optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
}

V. Bilo,
M. Flammini,
G. Monaco,
and L. Moscardelli.
On the performances of Nash equilibria in isolation games.
Journal of Combinatorial Optimization,
22:378391,
2011.
Note: Special Issue: Selected Papers from the 15th International Computing and Combinatorics Conference.
[WWW
]
Abstract: 
We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148â159, 2008 ). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the playersâ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases. 
@article{BFM+11,
author = {Bilo, V. and Flammini, M. and Monaco, G. and Moscardelli, L.},
title = {On the performances of Nash equilibria in isolation games},
journal = {Journal of Combinatorial Optimization},
publisher = {Springer Netherlands},
issn = {13826905},
pages = {378391},
volume = {22},
issue = {3},
url = {http://dx.doi.org/10.1007/s1087801093003},
note = {Special Issue: Selected Papers from the 15th International Computing and Combinatorics Conference},
abstract = {We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148â159, 2008 ). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the playersâ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.},
year = {2011},
xpays = {IT},
sorte = "revint",
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
}

B. Bresar,
F. Kardos,
J. Katrenic,
and G. Semanisin.
Minimum $k$path vertex cover.
Discrete Applied Mathematics,
159(12):11891195,
2011.
[PDF
]
Abstract: 
A subset $S$ of vertices of a graph $G$ is called a {\em $k$path vertex cover} if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$path vertex cover in $G$. It is shown that the problem of determining $\psi_k(G)$ is NPhard for each $k\geq2$, while for trees the problem can be solved in linear time.
We investigate upper bounds on the value of $\psi_k(G)$ and provide several estimations and exact values of $\psi_k(G)$. We also prove that $\psi_3(G)\le (2n+m)/6$, for every graph $G$ with $n$ vertices and $m$ edges. 
@article{BKK+11,
author = {Bre{\v{s}}ar, B. and Kardo{\v{s}}, F. and Katreni{\v{c}}, J. and Semani{\v{s}}in, G. },
title = {Minimum $k$path vertex cover},
journal = {Discrete Applied Mathematics},
year = {2011},
volume = {159},
number = {12},
pages = {11891195},
abstract = {A subset $S$ of vertices of a graph $G$ is called a {\em $k$path vertex cover} if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$path vertex cover in $G$. It is shown that the problem of determining $\psi_k(G)$ is NPhard for each $k\geq2$, while for trees the problem can be solved in linear time.
We investigate upper bounds on the value of $\psi_k(G)$ and provide several estimations and exact values of $\psi_k(G)$. We also prove that $\psi_3(G)\le (2n+m)/6$, for every graph $G$ with $n$ vertices and $m$ edges. },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/BKK+11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {SI, SK},
sorte = "revint",
}

C. Caillouet,
S. Pérennes,
and H. Rivano.
Framework for Optimizing the Capacity of Wireless Mesh Networks.
Computer Communications,
34(13):16451659,
2011.
[WWW
]
Keywords:
Wireless mesh networks,
capacity,
routing,
scheduling,
linear programming,
column and cut generation..
Abstract: 
In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks (WMNs) dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A crosslayer optimization of these problems allows the routing to take into account contentions due to radio interference. We present a generic Mixed Integer Linear Programing description of the congurations of a given WMN, addressing gateway placement, routing, and scheduling optimizations. We then develop new optimization models that can take into account a large variety of radio interference models, and QoS requirements on the routing. We also provide efficient resolution methods that deal with realistic size instances. It allows to work around the combinatoric of simultaneously achievable transmissions and point out a critical region in the network bounding the network achievable capacity. Based upon strong duality arguments, it is then possible to restrict the
computation to a bounded area. It allows for computing solutions very efficiently on large networks. 
@article{CPR11,
author = {C. Caillouet and S. P\'erennes and H. Rivano},
title = {{Framework for Optimizing the Capacity of Wireless Mesh Networks}},
journal = {{Computer Communications}},
publisher = {Elsevier},
year = {2011},
volume = {34},
number = {13},
pages = {16451659},
keywords = {Wireless mesh networks, capacity, routing, scheduling, linear programming, column and cut generation.},
url = {http://dx.doi.org/10.1016/j.comcom.2011.03.002},
#url = {http://hal.inria.fr/inria00572967/en},
abstract = {In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks (WMNs) dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A crosslayer optimization of these problems allows the routing to take into account contentions due to radio interference. We present a generic Mixed Integer Linear Programing description of the congurations of a given WMN, addressing gateway placement, routing, and scheduling optimizations. We then develop new optimization models that can take into account a large variety of radio interference models, and QoS requirements on the routing. We also provide efficient resolution methods that deal with realistic size instances. It allows to work around the combinatoric of simultaneously achievable transmissions and point out a critical region in the network bounding the network achievable capacity. Based upon strong duality arguments, it is then possible to restrict the
computation to a bounded area. It allows for computing solutions very efficiently on large networks.},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "revint",
}

J. Chalopin,
V. Chepoi,
N. Nisse,
and Y. Vaxès.
Cop and robber games when the robber can hide and ride.
SIAM Journal of Discrete Maths.,
25(1):333359,
2011.
[WWW
] [PDF
]
Abstract: 
In the classical cop and robber game, two players, the cop
C and the robber R, move alternatively along edges of a finite graph
G=(V,E). The cop captures the robber if both players are on the same
vertex at the same moment of time. A graph G is called cop win if the
cop always captures the robber after a finite number of
steps. Nowakowski, Winkler (1983) and Quilliot (1983) characterized
the copwin graphs as graphs admitting a dismantling scheme. In this
paper, we characterize in a similar way the copwin graphs in the game
in which the cop and the robber move at different speeds s' and s,
s'<= s. We also investigate several dismantling schemes necessary or
sufficient for the copwin graphs in the game in which the robber is
visible only every k moves for a fixed integer k>1. We characterize
the graphs which are copwin for any value of k. 
@article{CCN+11,
author = {Chalopin, J. and Chepoi, V. and Nisse, N. and Vax\`es, Y.},
title = {Cop and robber games when the robber can hide and ride},
journal = {SIAM Journal of Discrete Maths.},
year = {2011},
volume = {25},
number = {1},
pages = {333359},
abstract = {In the classical cop and robber game, two players, the cop
C and the robber R, move alternatively along edges of a finite graph
G=(V,E). The cop captures the robber if both players are on the same
vertex at the same moment of time. A graph G is called cop win if the
cop always captures the robber after a finite number of
steps. Nowakowski, Winkler (1983) and Quilliot (1983) characterized
the copwin graphs as graphs admitting a dismantling scheme. In this
paper, we characterize in a similar way the copwin graphs in the game
in which the cop and the robber move at different speeds s' and s,
s'<= s. We also investigate several dismantling schemes necessary or
sufficient for the copwin graphs in the game in which the robber is
visible only every k moves for a fixed integer k>1. We characterize
the graphs which are copwin for any value of k.},
url = {http://hal.archivesouvertes.fr/inria00448243/fr/},
pdf = {http://hal.archivesouvertes.fr/docs/00/44/82/43/PDF/RR7178.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
}

N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
Theoretical Computer Science (TCS),
412(35):46754687,
August 2011.
[WWW
] [PDF
]
Abstract: 
We consider a variant of the graph searching games that models the
routing reconfiguration problem in WDM networks. In the digraph
processing game, a team of agents aims at {\it processing}, or
clearing, the vertices of a digraph~$D$. We are interested in two
different measures: 1) the total number of agents used, and 2) the
total number of vertices occupied by an agent during the processing
of $D$. These measures respectively correspond to the maximum number
of simultaneous connections interrupted and to the total number of
interruptions during a routing reconfiguration
in a WDM network.
Previous works have studied the problem of independently minimizing
each of these parameters. In particular, the
corresponding minimization problems are APXhard, and the first one
is known not to be in APX. In this paper, we give several
complexity results and study tradeoffs between these conflicting
objectives. In particular, we show that minimizing one of these
parameters while the other is constrained is NPcomplete. Then, we
prove that there exist some digraphs for which minimizing one of
these objectives arbitrarily impairs the quality of the solution for
the other one. We show that such bad tradeoffs may happen even for a
basic class of digraphs. On the other hand, we exhibit classes of
graphs for which good tradeoffs can be achieved. We finally detail
the relationship between this game and the routing reconfiguration
problem. In particular, we prove that any instance of the processing
game, i.e. any digraph, corresponds to an instance of the routing
reconfiguration problem. 
@Article{CCM+11,
author = {N. Cohen and D. Coudert and D. Mazauric and N. Nepomuceno and N. Nisse},
title = {Tradeoffs in process strategy games with application in the {WDM} reconfiguration problem},
journal = {Theoretical Computer Science (TCS)},
year = {2011},
volume = {412},
number = {35},
pages = {46754687},
month = aug,
url = {http://dx.doi.org/10.1016/j.tcs.2011.05.002},
pdf = {http://hal.inria.fr/docs/00/59/25/07/PDF/papernoformat.pdf},
abstract = { We consider a variant of the graph searching games that models the
routing reconfiguration problem in WDM networks. In the digraph
processing game, a team of agents aims at {\it processing}, or
clearing, the vertices of a digraph~$D$. We are interested in two
different measures: 1) the total number of agents used, and 2) the
total number of vertices occupied by an agent during the processing
of $D$. These measures respectively correspond to the maximum number
of simultaneous connections interrupted and to the total number of
interruptions during a routing reconfiguration
in a WDM network.
Previous works have studied the problem of independently minimizing
each of these parameters. In particular, the
corresponding minimization problems are APXhard, and the first one
is known not to be in APX. In this paper, we give several
complexity results and study tradeoffs between these conflicting
objectives. In particular, we show that minimizing one of these
parameters while the other is constrained is NPcomplete. Then, we
prove that there exist some digraphs for which minimizing one of
these objectives arbitrarily impairs the quality of the solution for
the other one. We show that such bad tradeoffs may happen even for a
basic class of digraphs. On the other hand, we exhibit classes of
graphs for which good tradeoffs can be achieved. We finally detail
the relationship between this game and the routing reconfiguration
problem. In particular, we prove that any instance of the processing
game, i.e. any digraph, corresponds to an instance of the routing
reconfiguration problem.},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays={DK},
sorte = "revint",
}

N. Cohen and F. Havet.
Linear and 2Frugal Choosability of Graphs of Small Maximum Average Degree.
Graphs and Combinatorics,
27(6):831849,
2011.
[WWW
] [PDF
]
Abstract: 
A proper vertex colouring of a graph $G$ is {\it 2frugal} (resp. {\it linear}) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph $G$ is {\it 2frugally} (resp. {\it linearly}) {\it $L$colourable} if for a given list assignment $L:V(G)\mapsto 2^{\mathbb N}$, there exists a 2frugal (resp. linear) colouring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V(G)$. If $G$ is 2frugally (resp. linearly) $L$list colourable for any list assignment such that $L(v)\ge k$ for all $v\inV(G)$, then $G$ is {\it 2frugally} (resp. {\it linearly}) {\it $k$choosable}. In this paper, we improve some bounds on the 2frugal choosability and linear choosability of graphs with small maximum average degree. 
@article{CoHa11,
author = {N. Cohen and F. Havet},
title = {Linear and 2Frugal Choosability of Graphs of Small Maximum Average Degree},
journal = {Graphs and Combinatorics},
volume = {27},
number = {6},
year = {2011},
pages = {831849},
abstract = {
A proper vertex colouring of a graph $G$ is {\it 2frugal} (resp. {\it linear}) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph $G$ is {\it 2frugally} (resp. {\it linearly}) {\it $L$colourable} if for a given list assignment $L:V(G)\mapsto 2^{\mathbb N}$, there exists a 2frugal (resp. linear) colouring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V(G)$. If $G$ is 2frugally (resp. linearly) $L$list colourable for any list assignment such that $L(v)\ge k$ for all $v\inV(G)$, then $G$ is {\it 2frugally} (resp. {\it linearly}) {\it $k$choosable}. In this paper, we improve some bounds on the 2frugal choosability and linear choosability of graphs with small maximum average degree.},
URL={http://hal.inria.fr/inria00459692/},
PDF = {http://hal.inria.fr/docs/00/45/96/92/PDF/RR7213.pdf},
sorte = {revint},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
}

D. Coudert,
F. Giroire,
and I. Sau.
Circuits in graphs through a prescribed set of ordered vertices.
Journal of Interconnection Networks (JOIN),
11(34):121141,
2011.
[WWW
] [PDF
]
Abstract: 
A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\ldots,v_{k+1}\}$ such that $v_1=v_{k+1}$ and $\{v_i,v_{i+1}\} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edgesimple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of a graph $G$, there exists an edgesimple circuit visiting the $k$ vertices in the prescribed order? We first study the case when $G$ has maximum degree at most 3, establishing the value of $k$ for several subcases, such as when $G$ is planar or 3vertexconnected. Our main result is that $k=10$ in infinite square grids. To prove this, we introduce a methodology based on the notion of core graph, in order to reduce the number of possible vertex configurations, and then we test each one of the resulting configurations with an Integer Linear Program (ILP) solver. 
@article{CGS11,
author = {D. Coudert and F. Giroire and I. Sau},
title = {Circuits in graphs through a prescribed set of ordered vertices},
journal = {Journal of Interconnection Networks (JOIN)},
year = {2011},
volume = {11},
number = {34},
pages = {121141},
abstract = {A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\ldots,v_{k+1}\}$ such that $v_1=v_{k+1}$ and $\{v_i,v_{i+1}\} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edgesimple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of a graph $G$, there exists an edgesimple circuit visiting the $k$ vertices in the prescribed order? We first study the case when $G$ has maximum degree at most 3, establishing the value of $k$ for several subcases, such as when $G$ is planar or 3vertexconnected. Our main result is that $k=10$ in infinite square grids. To prove this, we introduce a methodology based on the notion of core graph, in order to reduce the number of possible vertex configurations, and then we test each one of the resulting configurations with an Integer Linear Program (ILP) solver.},
url = {http://dx.doi.org/10.1142/S0219265910002763},
pdf = {http://hal.inria.fr/docs/00/58/55/61/PDF/joinfinalnoformat.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
}

D. Coudert and JS. Sereni.
Characterization of graphs and digraphs with small process number.
Discrete Applied Mathematics (DAM),
159(11):10941109,
July 2011.
[WWW
] [PDF
]
Abstract: 
We introduce the process number of a digraph as a tool to study
rerouting issues in \wdm networks. This parameter is closely related
to the vertex separation (or pathwidth). We consider the recognition
and the characterization of (di)graphs with small process number. In
particular, we give a linear time algorithm to recognize (and
process) graphs with process number at most $2$, along with a
characterization in terms of forbidden minors, and a structural
description. As for digraphs with process number $2$, we exhibit a
characterization that allows one to recognize (and process) them in
polynomial time. 
@article{CoSe11,
author = {D. Coudert and JS. Sereni},
title = {Characterization of graphs and digraphs with small process number},
journal = {Discrete Applied Mathematics (DAM)},
year = {2011},
volume = {159},
number = {11},
pages = {10941109},
month = {jul},
abstract = {We introduce the process number of a digraph as a tool to study
rerouting issues in \wdm networks. This parameter is closely related
to the vertex separation (or pathwidth). We consider the recognition
and the characterization of (di)graphs with small process number. In
particular, we give a linear time algorithm to recognize (and
process) graphs with process number at most $2$, along with a
characterization in terms of forbidden minors, and a structural
description. As for digraphs with process number $2$, we exhibit a
characterization that allows one to recognize (and process) them in
polynomial time.},
url = {http://dx.doi.org/10.1016/j.dam.2011.03.010},
pdf = {http://hal.inria.fr/docs/00/58/77/17/PDF/damnoformat.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays={},
sorte = "revint",
}

J. Czap,
S. Jendrol',
and F. Kardos.
Facial parity edge colouring.
Ars Mathematica Contemporanea,
4(2):255269,
2011.
[PDF
]
Abstract: 
A \emph{facial parity edge colouring} of a connected bridgeless plane graph is such an edge colouring in which no two faceadjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face $\alpha$ and each colour $c$, either no edge or an odd number of edges incident with $\alpha$ is coloured with $c$. From Vizing's theorem it follows that every $3$connected plane graph has a such colouring with at most $\Delta^* +1$ colours, where $\Delta^* $ is the size of the largest face. In this paper we prove that any connected bridgeless plane graph has a facial parity edge colouring with at most $92$ colours. 
@article{CJK11,
author = {Czap, J. and S. Jendrol' and Kardo{\v{s}}, F. },
title = {Facial parity edge colouring},
journal = {Ars Mathematica Contemporanea},
year = {2011},
volume = {4},
number = {2},
pages = {255269},
abstract = {A \emph{facial parity edge colouring} of a connected bridgeless plane graph is such an edge colouring in which no two faceadjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face $\alpha$ and each colour $c$, either no edge or an odd number of edges incident with $\alpha$ is coloured with $c$. From Vizing's theorem it follows that every $3$connected plane graph has a such colouring with at most $\Delta^* +1$ colours, where $\Delta^* $ is the size of the largest face. In this paper we prove that any connected bridgeless plane graph has a facial parity edge colouring with at most $92$ colours. },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/CJK11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {SK},
sorte = "revint",
}

J. Czap,
S. Jendrol',
and F. Kardos.
On the strong parity chromatic number.
Discussiones Mathematicae Graph Theory,
31:587600,
2011.
[PDF
]
Abstract: 
A vertex colouring of a 2connected plane graph $G$ is a strong parity vertex colouring if for every face $f$ and each colour $c$, the number of vertices incident with $f$ coloured by $c$ is either zero or odd. Czap et al. [Discrete Math. 311 (2011) 512Â520] proved that every 2connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs 
@article{CJKa11,
author = {Czap, J. and S. Jendrol' and Kardo{\v{s}}, F. },
title = {On the strong parity chromatic number},
journal = {Discussiones Mathematicae Graph Theory},
year = {2011},
volume = {31},
number = {},
pages = {587600},
abstract = {A vertex colouring of a 2connected plane graph $G$ is a strong parity vertex colouring if for every face $f$ and each colour $c$, the number of vertices incident with $f$ coloured by $c$ is either zero or odd. Czap et al. [Discrete Math. 311 (2011) 512Â520] proved that every 2connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/CJKa11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {SK},
sorte = "revint",
}

J. Czap,
S. Jendrol',
F. Kardos,
and J. Miskuf.
Looseness of Plane Graphs.
Graphs and Combinatorics,
27(1):7385,
2011.
[PDF
]
Abstract: 
A face of a vertex coloured plane graph is called {\em loose} if the number of colours used on its vertices is at least three. The {\em looseness} of a plane graph $G$ is the minimum $k$ such that any surjective $k$colouring involves a loose face.
In this paper we prove that the looseness of a connected plane graph $G$ equals the maximum number of vertex disjoint cycles in a dual graph $G^*$ increased by 2. We also show upper and lower bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graph. These bounds improve the result of Negami for the looseness of plane triangulations.
We also present infinite classes of graphs where the equalities are attained. 
@article{CJK+11,
author = {Czap, J. and S. Jendrol' and Kardo{\v{s}}, F. and Mi{\v{s}}kuf, J. },
title = {Looseness of Plane Graphs},
journal = {Graphs and Combinatorics},
year = {2011},
volume = {27},
number = {1},
pages = {7385},
abstract = {A face of a vertex coloured plane graph is called {\em loose} if the number of colours used on its vertices is at least three. The {\em looseness} of a plane graph $G$ is the minimum $k$ such that any surjective $k$colouring involves a loose face.
In this paper we prove that the looseness of a connected plane graph $G$ equals the maximum number of vertex disjoint cycles in a dual graph $G^*$ increased by 2. We also show upper and lower bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graph. These bounds improve the result of Negami for the looseness of plane triangulations.
We also present infinite classes of graphs where the equalities are attained. },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/CJK+11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {SK},
sorte = "revint",
}

G. D'Angelo,
Gabriele Di Stefano,
Alfredo Navarra,
and Cristina Pinotti.
Recoverable Robust Timetables: An Algorithmic Approach on Trees.
IEEE Transactions on Computers,
60(3):433  446,
March 2011.
[WWW
] [PDF
]
Abstract: 
In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared" if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality
of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NPhard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm. 
@article{DDN+11,
hal_id = {hal00643980},
url = {http://hal.inria.fr/hal00643980/en/},
title = {{Recoverable Robust Timetables: An Algorithmic Approach on Trees}},
author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo and Pinotti, Cristina},
abstract = {{In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared" if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality
of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NPhard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm.}},
language = {English},
publisher = {IEEE},
pages = {433  446},
journal = {IEEE Transactions on Computers},
volume = {60},
number = {3 },
doi = {10.1109/TC.2010.142 },
year = {2011},
month = Mar,
pdf = {http://hal.inria.fr/hal00643980/PDF/RobustTree.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "revint",
}

O. Dalle.
Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering?  Part 1.
Modeling & Simulation Magazine,
11(3),
07 2011.
Note: Online publication.
[WWW
] [PDF
]
Abstract: 
This twopart article addresses the issues concerning the building
of new simulation software by either reusing existing general purpose software
products and frameworks or by writing the simulation software from scratch.
As a means of discussing the use of existing software, this first part
escribes a selected list of such existing software: the Eclipse IDE as
graphical user frontend, Maven for the management and building of projects,
Bonita for supporting simulation workflows, Ruby on Rails and its Hobo
extension to provide online persistence, and the Fractal Component Model for
supporting the popular ComponentBased Modeling \& Simulation approach. The
second part, to be published in the next issue of the \emph{M\&S Magazine},
will further explore some interesting features found in the selected software
solutions, and discuss their benefits when applied to simulation. 
@article{Dal11a,
author = {O. Dalle},
title = {Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering?  Part 1},
journal = {Modeling \& Simulation Magazine},
publisher = {Sage Publishers},
year = {2011},
volume = {11},
number = {3},
month = {07},
note = {Online publication},
url = {http://hal.inria.fr/inria00638553},
PDF = {ftp://ftpsop.inria.fr/mascotte/Publications/Dal11.pdf},
abstract = {This twopart article addresses the issues concerning the building
of new simulation software by either reusing existing general purpose software
products and frameworks or by writing the simulation software from scratch.
As a means of discussing the use of existing software, this first part
escribes a selected list of such existing software: the Eclipse IDE as
graphical user frontend, Maven for the management and building of projects,
Bonita for supporting simulation workflows, Ruby on Rails and its Hobo
extension to provide online persistence, and the Fractal Component Model for
supporting the popular ComponentBased Modeling \& Simulation approach. The
second part, to be published in the next issue of the \emph{M\&S Magazine},
will further explore some interesting features found in the selected software
solutions, and discuss their benefits when applied to simulation. },
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
sorte = "confint",
}

O. Dalle.
Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering?  Part 2.
Modeling & Simulation Magazine,
11(4),
10 2011.
Note: Online publication.
[WWW
]
Abstract: 
This twopart article addresses the issues concerning the building
of new simulation software by either reusing existing general purpose software
products and frameworks or by writing the simulation software from scratch.
As a means of discussing the use of existing software, this first part
escribes a selected list of such existing software: the Eclipse IDE as
graphical user frontend, Maven for the management and building of projects,
Bonita for supporting simulation workflows, Ruby on Rails and its Hobo
extension to provide online persistence, and the Fractal Component Model for
supporting the popular ComponentBased Modeling \& Simulation approach. The
second part, to be published in the next issue of the \emph{M\&S Magazine},
will further explore some interesting features found in the selected software
solutions, and discuss their benefits when applied to simulation. 
@article{Dal11b,
author = {O. Dalle},
title = {Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering?  Part 2},
journal = {Modeling \& Simulation Magazine},
publisher = {Sage Publishers},
year = {2011},
volume = {11},
number = {4},
month = {10},
note = {Online publication},
url = {http://hal.inria.fr/inria00638555_v1/},
abstract = {This twopart article addresses the issues concerning the building
of new simulation software by either reusing existing general purpose software
products and frameworks or by writing the simulation software from scratch.
As a means of discussing the use of existing software, this first part
escribes a selected list of such existing software: the Eclipse IDE as
graphical user frontend, Maven for the management and building of projects,
Bonita for supporting simulation workflows, Ruby on Rails and its Hobo
extension to provide online persistence, and the Fractal Component Model for
supporting the popular ComponentBased Modeling \& Simulation approach. The
second part, to be published in the next issue of the \emph{M\&S Magazine},
will further explore some interesting features found in the selected software
solutions, and discuss their benefits when applied to simulation. },
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
sorte = "confint",
}

R. Erman,
F. Havet,
B. Lidicky,
and O. Pangrác.
5colouring graphs with 4 crossings.
SIAM Journal on Discrete Mathematics,
25(1):401422,
2011.
[PDF
]
Abstract: 
We disprove a conjecture of
Oporowski and Zhao stating that every graph with crossing number at most 5
and clique number at most 5 is 5colourable.
However, we show that every graph with crossing number at most 4 and
clique number at most 5 is 5colourable.
We also show some colourability results on graphs that can
be made planar by removing few edges.
In particular, we show that if there exists three edges whose removal
leaves the graph planar then it is $5$colourable. 
@article{EHL+11,
author = {R. Erman and F. Havet and B. Lidick{\'{y}} and O. Pangr\'ac},
title = {5colouring graphs with 4 crossings},
year = {2011},
volume = {25},
number = {1},
pages = {401422},
journal={SIAM Journal on Discrete Mathematics},
abstract = {We disprove a conjecture of
Oporowski and Zhao stating that every graph with crossing number at most 5
and clique number at most 5 is 5colourable.
However, we show that every graph with crossing number at most 4 and
clique number at most 5 is 5colourable.
We also show some colourability results on graphs that can
be made planar by removing few edges.
In particular, we show that if there exists three edges whose removal
leaves the graph planar then it is $5$colourable.},
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/EHL+11.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={CZ,SI},
sorte = "revint",
}

L. Esperet,
F. Kardos,
A. D. King,
D. Král',
and S. Norine.
Exponentially many perfect matchings in cubic graphs.
Advances in Mathematics,
227(4):16461664,
2011.
[PDF
]
Abstract: 
We show that every cubic bridgeless graph $G$ has at least $2^{V(G)/3656}$ perfect matchings. This confirms an old conjecture of Lov{\'{a}}sz and Plummer. 
@article{EKK+11,
author = {Esperet, L. and Kardo{\v{s}}, F. and King, A. D. and Kr{\'{a}}l', D. and Norine, S. },
title = {Exponentially many perfect matchings in cubic graphs},
journal = {Advances in Mathematics},
year = {2011},
volume = {227},
number = {4},
pages = {16461664},
abstract = {We show that every cubic bridgeless graph $G$ has at least $2^{V(G)/3656}$ perfect matchings. This confirms an old conjecture of Lov{\'{a}}sz and Plummer. },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/EKK+11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {CZ, SK, US},
sorte = "revint",
}

P. Giabbanelli and J. G. Peters.
Complex networks and epidemics.
Technique et Science Informatiques,
20(2):181212,
2011.
Abstract: 
The study of spreading processes, such as infectious diseases or
computer worms, is wellmotivated by its financial impact and
humanitarian aspects. A vast amount of research has emerged through the
theory of complex networks, that sheds light on the properties found in a
wide range of "realworld" networks. We review these properties in the
context of spreads, with an emphasis on the settings underlying some of
the major claims in the literature such as whether or not a scalefree
network is particularly prone to spreading phenomena. Stochastic models
have been well studied in the literature, and thus we focus on
deterministic models, highlighting the connections between the two
approaches. Finally, we classify immunization strategies into four
categories, which allows comparisons on common features from a computer
science perspective. Several topics for future work are suggested. For
example, it remains open whether immunization strategies, such as those
based on degree, benefit from complex network properties. 
@article{GiPe10,
author="P. Giabbanelli and J. G. Peters",
title="Complex networks and epidemics",
journal="Technique et Science Informatiques",
year={2011},
volume = {20},
number = {2},
pages = {181212},
month = {},
abstract={The study of spreading processes, such as infectious diseases or
computer worms, is wellmotivated by its financial impact and
humanitarian aspects. A vast amount of research has emerged through the
theory of complex networks, that sheds light on the properties found in a
wide range of "realworld" networks. We review these properties in the
context of spreads, with an emphasis on the settings underlying some of
the major claims in the literature such as whether or not a scalefree
network is particularly prone to spreading phenomena. Stochastic models
have been well studied in the literature, and thus we focus on
deterministic models, highlighting the connections between the two
approaches. Finally, we classify immunization strategies into four
categories, which allows comparisons on common features from a computer
science perspective. Several topics for future work are suggested. For
example, it remains open whether immunization strategies, such as those
based on degree, benefit from complex network properties.},
doi = {http://dx.doi.org/10.3166/tsi.30.181212},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "revnat",
}

F. Havet,
S. Jendrol',
R. Soták,
and E. Skrabul'áková.
Facial nonrepetitive edgecolouring of plane graphs.
Journal of Graph Theory,
66(1):3848,
2011.
[WWW
] [PDF
]
Abstract: 
A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em nonrepetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em nonrepetitive} if the sequence of colours of its edges is nonrepetitive. If $G$ is a plane graph, a {\em facial nonrepetitive edgecolouring} of $G$ is an edgecolouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is nonrepetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial nonrepetitive edgecolouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_f(G)$ in the cases when $G$ is a tree, a plane triangulation, a simple $3$connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound $4$ for trees is tight.

@article{HJS+11,
author = {F. Havet and S. Jendrol' and R. Sot{\'a}k and E. {\v{S}}krabul'{\'a}kov{\'a}},
title = {Facial nonrepetitive edgecolouring of plane graphs},
journal = {Journal of Graph Theory},
volume = {66},
number = {1},
year = {2011},
pages = {3848},
abstract = {A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em nonrepetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em nonrepetitive} if the sequence of colours of its edges is nonrepetitive. If $G$ is a plane graph, a {\em facial nonrepetitive edgecolouring} of $G$ is an edgecolouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is nonrepetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial nonrepetitive edgecolouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_f(G)$ in the cases when $G$ is a tree, a plane triangulation, a simple $3$connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound $4$ for trees is tight.
},
URL={http://hal.inria.fr/inria00366589/en/},
PDF = {http://hal.inria.fr/docs/00/36/65/89/PDF/RR6873.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "revint",
}

F. Havet,
M. Klazar,
J. Kratochvìl,
D. Kratsch,
and M. Liedloff.
Exact algorithms for L(2,1)labelling.
Algorithmica,
59(2):169194,
2011.
[PDF
]
Abstract: 
The notion of distance constrained graph labelings, motivated by the
Frequency Assignment Problem, reads as follows: A mapping from the
vertex set of a graph $G=(V,E)$ into an interval of integers
$\{0, \dots ,k\}$ is an $L(2,1)$labeling of $G$ of span $k$ if any two
adjacent vertices are mapped onto integers that are at least 2
apart, and every two vertices with a common neighbor are mapped onto
distinct integers. It is known that for any fixed $k\ge 4$, deciding
the existence of such a labeling is an NPcomplete problem. We
present exact exponential time algorithms that are faster than the
naive $O((k+1)^n)$ algorithm that would try all possible mappings.
The improvement is best seen in the first NPcomplete case of $k=4$
 here the running time of our algorithm is $O(1.3006^n)$. % $O(1.3161^n)$.
Furthermore we show that dynamic programming can be used to establish
0x1.57ca7bff74698p895n $O(c^n)$ algorithm to compute an optimal $L(2,1)$labeling, for a constant $c< 4$.
an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$labeling. 
@article{HKK+11,
author = {F. Havet and M. Klazar and J. Kratochv{\'{i}}l and D. Kratsch and M. Liedloff},
title = {Exact algorithms for L(2,1)labelling},
journal = {Algorithmica},
volume = {59},
number = {2},
year = {2011},
pages = {169194},
abstract = {The notion of distance constrained graph labelings, motivated by the
Frequency Assignment Problem, reads as follows: A mapping from the
vertex set of a graph $G=(V,E)$ into an interval of integers
$\{0, \dots ,k\}$ is an $L(2,1)$labeling of $G$ of span $k$ if any two
adjacent vertices are mapped onto integers that are at least 2
apart, and every two vertices with a common neighbor are mapped onto
distinct integers. It is known that for any fixed $k\ge 4$, deciding
the existence of such a labeling is an NPcomplete problem. We
present exact exponential time algorithms that are faster than the
naive $O((k+1)^n)$ algorithm that would try all possible mappings.
The improvement is best seen in the first NPcomplete case of $k=4$
 here the running time of our algorithm is $O(1.3006^n)$. % $O(1.3161^n)$.
Furthermore we show that dynamic programming can be used to establish
0x1.57ca7bff74698p895n $O(c^n)$ algorithm to compute an optimal $L(2,1)$labeling, for a constant $c< 4$.
an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$labeling.},
pdf = {http://hal.archivesouvertes.fr/docs/00/30/33/30/PDF/RR6587.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={CZ},
}

F. Kardos,
J. Katrenic,
and I. Schiermeyer.
On computing the minimum 3path vertex cover and dissociation number of graphs.
Theoretical Computer Science,
412(50):70097017,
2011.
[PDF
]
Abstract: 
The dissociation number of a graph $G$ is the number of vertices in a maximum size induced subgraph of $G$ with vertex degree at most 1. A $k$path vertex cover of a graph $G$ is a subset $S$ of vertices of $G$ such that every path of order $k$ in $G$ contains at least one vertex from $S$. The minimum $3$path vertex cover is a dual problem to the dissociation number. For this problem we present an exact algorithm with a running time of $\mathcal{O}^*(1.5171^n)$ on a graph with $n$ vertices.
We also provide a polynomial time randomized approximation algorithm with an expected approximation ratio of $\frac{23}{11}$ for the minimum $3$path vertex cover. 
@article{KKS11,
author = {Kardo{\v{s}}, F. and Katreni{\v{c}}, J. and Schiermeyer, I. },
title = {On computing the minimum 3path vertex cover and dissociation number of graphs},
journal = {Theoretical Computer Science},
year = {2011},
volume = {412},
number = {50},
pages = {70097017},
abstract = {The dissociation number of a graph $G$ is the number of vertices in a maximum size induced subgraph of $G$ with vertex degree at most 1. A $k$path vertex cover of a graph $G$ is a subset $S$ of vertices of $G$ such that every path of order $k$ in $G$ contains at least one vertex from $S$. The minimum $3$path vertex cover is a dual problem to the dissociation number. For this problem we present an exact algorithm with a running time of $\mathcal{O}^*(1.5171^n)$ on a graph with $n$ vertices.
We also provide a polynomial time randomized approximation algorithm with an expected approximation ratio of $\frac{23}{11}$ for the minimum $3$path vertex cover. },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/KKS11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {GE, SK},
sorte = "revint",
}

F. Kardos,
D. Král',
and J. Volec.
Fractional colorings of cubic graphs with large girth.
SIAM Journal on Discrete Mathematics,
25(3):14541476,
2011.
[PDF
]
Abstract: 
We show that every (sub)cubic $n$vertex graph with sufficiently large girth has fractional chromatic number at most $2.2978$ which implies that it contains an independent set of size at least $0.4352n$. Our bound on the independence number is valid to random cubic graphs as well as it improves existing lower bounds on the maximum cut in cubic graphs with large girth. 
@article{KKV11,
author = {Kardo{\v{s}}, F. and Kr{\'{a}}l', D. and Volec, J. },
title = {Fractional colorings of cubic graphs with large girth},
journal = {SIAM Journal on Discrete Mathematics},
year = {2011},
volume = {25},
number = {3},
pages = {14541476},
abstract = {We show that every (sub)cubic $n$vertex graph with sufficiently large girth has fractional chromatic number at most $2.2978$ which implies that it contains an independent set of size at least $0.4352n$. Our bound on the independence number is valid to random cubic graphs as well as it improves existing lower bounds on the maximum cut in cubic graphs with large girth. },
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/KKV11.pdf},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
xpays = {CZ, SK},
sorte = "revint",
}

J. Araujo,
JC. Bermond,
F. Giroire,
F. Havet,
D. Mazauric,
and R. Modrzejewski.
Weighted Improper Colouring.
In C. S. Iliopoulos and W. F. Smyth, editors,
Combinatorial Algorithms,
volume 7056 of Lecture Notes in Computer Science,
Victoria, Canada,
pages 118,
June 2011.
Springer Berlin Heidelberg.
[WWW
] [PDF
]
Abstract: 
In this paper, we study a colouring problem motivated by a
practical frequency assignment problem and up to our best
knowledge new. In wireless networks, a node interferes with the
other nodes the level of interference depending on numerous
parameters: distance between the nodes, geographical topography,
obstacles, etc. We model this with a weighted graph $G$ where the
weights on the edges represent the noise (interference) between the
two endnodes. The total interference in a node is then the sum of
all the noises of the nodes emitting on the same frequency. A
weighted $t$improper $k$colouring of $G$ is a $k$colouring of the
nodes of $G$ (assignment of $k$ frequencies) such that the
interference at each node does not exceed some threshold
$t$. The Weighted Improper Colouring problem, that we consider here
consists in determining the weighted $t$improper chromatic number
defined as the minimum integer $k$ such that $G$ admits a weighted
$t$improper $k$colouring. We also consider the dual problem, denoted the
Threshold Improper Colouring problem, where given a number $k$ of
colours (frequencies) we want to determine the minimum real $t$ such
that $G$ admits a weighted $t$improper $k$colouring. We show that
both problems are NPhard and first present general upper bounds; in
particular we show a generalisation of Lov\'asz's Theorem for the
weighted $t$improper chromatic number. We then show how to
transform an instance of the Threshold Improper Colouring problem
into another equivalent one where the weights are either 1 or $M$,
for a sufficient big value $M$. Motivated by the original
application, we study a special interference model on various grids
(square, triangular, hexagonal) where a node produces a noise of
intensity 1 for its neighbours and a noise of intensity 1/2 for the
nodes that are at distance 2. Consequently, the problem consists of
determining the weighted $t$improper chromatic number when $G$ is
the square of a grid and the weights of the edges are 1, if
their end nodes are adjacent in the grid, and 1/2 otherwise.
Finally, we model the problem using linear integer programming,
propose and test heuristic and exact BranchandBound algorithms on
random celllike graphs, namely the PoissonVoronoi tessellations. 
@InProceedings{ABG+11b,
author = {Araujo, J. and Bermond, JC. and Giroire, F. and Havet, F. and Mazauric, D. and Modrzejewski, R.},
title = {Weighted Improper Colouring},
booktitle = {Combinatorial Algorithms},
year = {2011},
address = {Victoria, Canada},
publisher= { Springer Berlin Heidelberg },
series= {Lecture Notes in Computer Science},
editor={Iliopoulos, C. S. and Smyth, W. F.},
month = {June},
volume= {7056},
pages= {118},
abstract = {In this paper, we study a colouring problem motivated by a
practical frequency assignment problem and up to our best
knowledge new. In wireless networks, a node interferes with the
other nodes the level of interference depending on numerous
parameters: distance between the nodes, geographical topography,
obstacles, etc. We model this with a weighted graph $G$ where the
weights on the edges represent the noise (interference) between the
two endnodes. The total interference in a node is then the sum of
all the noises of the nodes emitting on the same frequency. A
weighted $t$improper $k$colouring of $G$ is a $k$colouring of the
nodes of $G$ (assignment of $k$ frequencies) such that the
interference at each node does not exceed some threshold
$t$. The Weighted Improper Colouring problem, that we consider here
consists in determining the weighted $t$improper chromatic number
defined as the minimum integer $k$ such that $G$ admits a weighted
$t$improper $k$colouring. We also consider the dual problem, denoted the
Threshold Improper Colouring problem, where given a number $k$ of
colours (frequencies) we want to determine the minimum real $t$ such
that $G$ admits a weighted $t$improper $k$colouring. We show that
both problems are NPhard and first present general upper bounds; in
particular we show a generalisation of Lov\'asz's Theorem for the
weighted $t$improper chromatic number. We then show how to
transform an instance of the Threshold Improper Colouring problem
into another equivalent one where the weights are either 1 or $M$,
for a sufficient big value $M$. Motivated by the original
application, we study a special interference model on various grids
(square, triangular, hexagonal) where a node produces a noise of
intensity 1 for its neighbours and a noise of intensity 1/2 for the
nodes that are at distance 2. Consequently, the problem consists of
determining the weighted $t$improper chromatic number when $G$ is
the square of a grid and the weights of the edges are 1, if
their end nodes are adjacent in the grid, and 1/2 otherwise.
Finally, we model the problem using linear integer programming,
propose and test heuristic and exact BranchandBound algorithms on
random celllike graphs, namely the PoissonVoronoi tessellations.},
doi={10.1007/9783642250118_1},
url={http://dx.doi.org/10.1007/9783642250118_1},
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/ABG+11b.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
xpays = {BR},
}

J. Araujo,
V. Campos,
F. Giroire,
L. Sampaio,
and R. Soares.
On the hull number of some graph classes.
In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb'11),
volume 38 of Electronic Notes in Discrete Mathematics,
Budapest, Hungary,
pages 4955,
September 2011.
[WWW
] [PDF
]
Abstract: 
Given a graph G = (V, E), the closed interval of a pair of vertices u, v \in V ,
denoted by I[u, v], is the set of vertices that belongs to some shortest (u, v)path.
For a given S \subseteq V , let I[S] = u,v \in S I[u, v]. We say that S \subseteq V is a convex set if
I[S] = S.
The convex hull Ih [S] of a subset S \subseteq V is the smallest convex set that contains
S. We say that S is a hull set if Ih [S] = V . The cardinality of a minimum hull set
of G is the hull number of G, denoted by hn(G).
We show that deciding if hn(G) \leq k is an NPcomplete problem, even if G is
bipartite. We also prove that hn(G) can be computed in polynomial time for cactus
and P4 sparse graphs.

@InProceedings{ACGS+11b,
author = {J. Araujo and V. Campos and F. Giroire and L. Sampaio and R. Soares },
title = {On the hull number of some graph classes},
booktitle = {Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb'11)},
series = {Electronic Notes in Discrete Mathematics},
pages = {4955},
volume = {38},
year = {2011},
address = {Budapest, Hungary},
month = {September},
abstract = {Given a graph G = (V, E), the closed interval of a pair of vertices u, v \in V ,
denoted by I[u, v], is the set of vertices that belongs to some shortest (u, v)path.
For a given S \subseteq V , let I[S] = u,v \in S I[u, v]. We say that S \subseteq V is a convex set if
I[S] = S.
The convex hull Ih [S] of a subset S \subseteq V is the smallest convex set that contains
S. We say that S is a hull set if Ih [S] = V . The cardinality of a minimum hull set
of G is the hull number of G, denoted by hn(G).
We show that deciding if hn(G) \leq k is an NPcomplete problem, even if G is
bipartite. We also prove that hn(G) can be computed in polynomial time for cactus
and P4 sparse graphs.
},
url={http://www.sciencedirect.com/science/article/pii/S1571065311000783},
pdf={ftp://ftpsop.inria.fr/mascotte/Publications/ACGS+11b.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays = {BR},
sorte = "confint",
}

J. Araujo,
F. Giroire,
and J. Monteiro.
Hybrid Approaches for Distributed Storage Systems.
In Proceedings of Fourth International Conference on Data Management in Grid and P2P Systems (Globe'11),
Toulouse, France,
September 2011.
[WWW
] [PDF
]
Abstract: 
Distributed or peertopeer storage solutions rely on the in
troduction of redundant data to be faulttolerant and to achieve high
reliability. One way to introduce redundancy is by simple replication.
This strategy allows an easy and fast access to data, and a good band
width efficiency to repair the missing redundancy when a peer leaves or
fails in high churn systems.
However, it is known that erasure codes, like ReedSolomon, are an effi
cient solution in terms of storage space to obtain high durability when
compared to replication.
Recently, the Regenerating Codes were proposed as an improvement of
erasure codes to better use the available bandwidth when reconstructing
the missing information.
In this work, we compare these codes with two hybrid approaches. The
first was already proposed and mixes erasure codes and replication. The
second one is a new proposal that we call Double Coding. We compare
these approaches with the traditional ReedSolomon code and also Re
generating Codes from the point of view of availability, durability and
storage space. This comparison uses Markov Chain Models that take into
account the reconstruction time of the systems.

@InProceedings{AGM11,
author = {J. Araujo and F. Giroire and J. Monteiro },
title = {Hybrid Approaches for Distributed Storage Systems},
booktitle = {Proceedings of Fourth International Conference on Data Management in Grid and P2P Systems (Globe'11)},
year = {2011},
address = {Toulouse, France},
month = {September},
abstract = {Distributed or peertopeer storage solutions rely on the in
troduction of redundant data to be faulttolerant and to achieve high
reliability. One way to introduce redundancy is by simple replication.
This strategy allows an easy and fast access to data, and a good band
width efficiency to repair the missing redundancy when a peer leaves or
fails in high churn systems.
However, it is known that erasure codes, like ReedSolomon, are an effi
cient solution in terms of storage space to obtain high durability when
compared to replication.
Recently, the Regenerating Codes were proposed as an improvement of
erasure codes to better use the available bandwidth when reconstructing
the missing information.
In this work, we compare these codes with two hybrid approaches. The
first was already proposed and mixes erasure codes and replication. The
second one is a new proposal that we call Double Coding. We compare
these approaches with the traditional ReedSolomon code and also Re
generating Codes from the point of view of availability, durability and
storage space. This comparison uses Markov Chain Models that take into
account the reconstruction time of the systems.
},
PDF={ftp://ftpsop.inria.fr/mascotte/Publications/AGM11.pdf},
url = {http://hal.inria.fr/inria00635781/fr/},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays = {BR},
sorte = "confint",
}

J. BangJensen,
F. Havet,
and N. Trotignon.
Finding an induced subdivision of a digraph.
In VI LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS 2011),
volume 37,
Bariloche, Argentina,
pages 0914,
04 2011.
Abstract: 
We consider the following problem for oriented graphs and digraphs:
Given an oriented graph (digraph) $G$, does it contain an induced
subdivision of a prescribed digraph $D$? The complexity of
this problem depends on $D$ and on whether $H$ must be an oriented
graph or is allowed to contain 2cycles. We give a number of examples of polynomial instances as well as several NPcompleteness proofs.

@InProceedings{BHT11,
author = {J. BangJensen and F. Havet and N. Trotignon},
title = {Finding an induced subdivision of a digraph},
year = {2011},
booktitle = {VI LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS 2011)},
journal = {Electronic Notes on Discrete Mathematics},
pages = {0914},
volume = {37},
address = {Bariloche, Argentina},
month = {04},
abstract = {We consider the following problem for oriented graphs and digraphs:
Given an oriented graph (digraph) $G$, does it contain an induced
subdivision of a prescribed digraph $D$? The complexity of
this problem depends on $D$ and on whether $H$ must be an oriented
graph or is allowed to contain 2cycles. We give a number of examples of polynomial instances as well as several NPcompleteness proofs.
},
sorte = "confint",
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={DK},
}

Sanjoy Baruah, K.,
Vincenzo Bonifaci,
G. D'Angelo,
Alberto MarchettiSpaccamela,
Suzanne Ster, Van Der,
and Leen Stougie.
MixedCriticality Scheduling of Sporadic Task Systems.
In Camil Demetrescu and Magnús M. Halldórsson, editors,
19th Annual European Symposium on Algorithms (ESA 2011),
volume 6942 of Lecture Notes in Computer Science,
Saarbruecken, Germany,
pages 555566,
August 2011.
Springer.
[WWW
] [PDF
]
Abstract: 
We consider the scheduling of mixedcriticality task systems, that is, systems where each task to be scheduled has multiple levels of worstcase execution time estimates. We design a scheduling algorithm, EDFVD, whose effectiveness we analyze using the processor speedup metric: we show that any 2level task system that is schedulable on a unitspeed processor is correctly scheduled by EDFVD using speed $\phi$; here $\phi$ 2 criticality levels.We finally consider 2level instances on m identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2level task system. 
@inproceedings{BBD+11b,
hal_id = {hal00643987},
url = {http://hal.inria.fr/hal00643987/en/},
title = {{MixedCriticality Scheduling of Sporadic Task Systems}},
author = {Baruah, K., Sanjoy and Bonifaci, Vincenzo and G. D'Angelo and MarchettiSpaccamela, Alberto and Ster, Van Der, Suzanne and Stougie, Leen},
abstract = {{We consider the scheduling of mixedcriticality task systems, that is, systems where each task to be scheduled has multiple levels of worstcase execution time estimates. We design a scheduling algorithm, EDFVD, whose effectiveness we analyze using the processor speedup metric: we show that any 2level task system that is schedulable on a unitspeed processor is correctly scheduled by EDFVD using speed $\phi$; here $\phi$ 2 criticality levels.We finally consider 2level instances on m identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2level task system.}},
language = {English},
booktitle = {{19th Annual European Symposium on Algorithms (ESA 2011)}},
publisher = {Springer},
pages = {555566},
address = {Saarbruecken, Germany},
volume = {6942},
editor = {Camil Demetrescu and Magn{\'u}s M. Halld{\'o}rsson },
series = {Lecture Notes in Computer Science },
doi = {10.1007/9783642237195\_47 },
year = {2011},
month = Aug,
pdf = {http://hal.inria.fr/hal00643987/PDF/MixedTasks.pdf},
xpays = {US,IT,NL,IN},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

J. Beauquier,
P. Blanchard,
J. Burman,
and S. Delaet.
Computing Time Complexity of Population Protocols with Cover Times  the ZebraNet Example.
In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2011,
Lecture Notes in Computer Science,
pages 4761,
2011.
Springer.
[WWW
]
Abstract: 
Population protocols are a communication model for large
sensor networks with resourcelimited mobile agents. The agents move
asynchronously and communicate via pairwise interactions. The original
fairness assumption of this model involves a high level of asynchrony
and prevents an evaluation of the convergence time of a protocol (via
deterministic means). The introduction of some "partial synchrony" in
the model, under the form of cover times, is an extension that allows
evaluating the time complexities.
In this paper, we take advantage of this extension and study a data
collection protocol used in the ZebraNet project for the wildlife tracking
of zebras in a reserve in central Kenya. In ZebraNet, sensors are attached
to zebras and the sensed data is collected regularly by a mobile base
station crossing the area. The data collection protocol of ZebraNet has
been analyzed through simulations, but to our knowledge, this is the rst
time, that a purely analytical study is presented. Our first result is that,
in the original protocol, some data may never be delivered to the base
station. We then propose two slightly modify ed and correct protocols and
we compute their worst case time complexities. Still, in both cases, the
result is far from the optimal. 
@inproceedings{BBB+11,
author = {J. Beauquier and P. Blanchard and J. Burman and S. Delaet},
title = {Computing Time Complexity of Population Protocols with Cover Times  the ZebraNet Example},
booktitle = {13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2011},
publisher = {Springer},
year = {2011},
series = {Lecture Notes in Computer Science},
abstract = {Population protocols are a communication model for large
sensor networks with resourcelimited mobile agents. The agents move
asynchronously and communicate via pairwise interactions. The original
fairness assumption of this model involves a high level of asynchrony
and prevents an evaluation of the convergence time of a protocol (via
deterministic means). The introduction of some "partial synchrony" in
the model, under the form of cover times, is an extension that allows
evaluating the time complexities.
In this paper, we take advantage of this extension and study a data
collection protocol used in the ZebraNet project for the wildlife tracking
of zebras in a reserve in central Kenya. In ZebraNet, sensors are attached
to zebras and the sensed data is collected regularly by a mobile base
station crossing the area. The data collection protocol of ZebraNet has
been analyzed through simulations, but to our knowledge, this is the rst
time, that a purely analytical study is presented. Our first result is that,
in the original protocol, some data may never be delivered to the base
station. We then propose two slightly modify ed and correct protocols and
we compute their worst case time complexities. Still, in both cases, the
result is far from the optimal.},
pages = {4761},
doi = {http://dx.doi.org/10.1007/9783642245503_6},
url = {http://hal.inria.fr/hal00639583/en/},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

J. Beauquier and J. Burman.
Selfstabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering.
In 15th International Conference On Principles Of Distributed Systems, OPODIS 2011,
Lecture Notes in Computer Science,
2011.
Springer.
[WWW
]
Abstract: 
This paper presents and proves correct two selfstabilizing deterministic
algorithms solving the mutual exclusion and the group mutual exclusion problems
in the model of population protocols with covering. In this variant of the
population protocol model, a local fairness is used and bounded state anonymous
mobile agents interact in pairs according to constraints expressed in terms of their
cover times. The cover time is an indicator of the "time" for an agent to communicate
with all the other agents. This indicator is expressed in the number of the
pairwise communications (events) and is unknown to agents. In the model, we
also assume the existence of a particular agent, the base station. In contrast with
the other agents, it has a memory size proportional to the number of the agents.
We prove that without this kind of assumption, the mutual exclusion problem has
no solution.
The algorithms in the paper use a phase clock tool. This is a synchronization
tool that was recently proposed in the model we use. For our needs, we extend
the functionality of this tool to support also phases with unbounded (but finite)
duration. This extension seems to be useful also in the future works. 
@inproceedings{BeBu11,
author = {J. Beauquier and J. Burman},
title = {Selfstabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering},
booktitle = {15th International Conference On Principles Of Distributed Systems, OPODIS 2011},
publisher = {Springer},
year = {2011},
series = {Lecture Notes in Computer Science},
abstract = {This paper presents and proves correct two selfstabilizing deterministic
algorithms solving the mutual exclusion and the group mutual exclusion problems
in the model of population protocols with covering. In this variant of the
population protocol model, a local fairness is used and bounded state anonymous
mobile agents interact in pairs according to constraints expressed in terms of their
cover times. The cover time is an indicator of the "time" for an agent to communicate
with all the other agents. This indicator is expressed in the number of the
pairwise communications (events) and is unknown to agents. In the model, we
also assume the existence of a particular agent, the base station. In contrast with
the other agents, it has a memory size proportional to the number of the agents.
We prove that without this kind of assumption, the mutual exclusion problem has
no solution.
The algorithms in the paper use a phase clock tool. This is a synchronization
tool that was recently proposed in the model we use. For our needs, we extend
the functionality of this tool to support also phases with unbounded (but finite)
duration. This extension seems to be useful also in the future works.},
url = {http://hal.inria.fr/hal00639651/en/},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

J. Beauquier,
J. Burman,
and V. Malykh.
ZebraNet Analysé dans le Modéle des Protocoles de Population.
In Ducourthial et Bertrand et Felber et Pascal, editor,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
]
Abstract: 
Nous \'etudions le protocole de collecte de donn\'ees du projet ZebraNet, dans le modÄle des protocoles de population. Dans ce
projet des capteurs sont attach\'es \'a une population de z\'ebres, en Afrique Centrale, et fournissent des donn\'ees aux biologistes
qui \'etudient leurs structures migratoires et comportementales. Nous montrons qu'un protocole voisin de celui utilis\'e dans ce
projet ne se termine pas. Cela entra\^ine que le protocole originel ne se termine pas non plus. Aussi proposons nous une
modification qui fournit la terminaison. Nous prouvons la correction de ce protocole modifi\'e et nous analysons sa complexit\'e
en temps au pire, dans le mod\'ele des protocoles de population avec temps de couverture. La comparaison de cette complexit\'e
avec celle du protocole optimal est tr\'es d\'efavorable.
Le protocole de collecte de donn\'ees de ZebraNet a fait l'objet de simulations, mais c'est la premi\'ere fois, \'a notre connaissance,
qu'est r\'ealis\'ee une \'etude purement analytique. 
@inproceedings{BBM11,
author = {Beauquier, J. and Burman, J. and Malykh, V.},
title = {ZebraNet Analys\'e dans le Mod\'ele des Protocoles de Population},
booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2011},
editor = {Ducourthial et Bertrand et Felber et Pascal},
address = {Cap Est\'erel, France},
abstract = {Nous \'etudions le protocole de collecte de donn\'ees du projet ZebraNet, dans le modÄle des protocoles de population. Dans ce
projet des capteurs sont attach\'es \'a une population de z\'ebres, en Afrique Centrale, et fournissent des donn\'ees aux biologistes
qui \'etudient leurs structures migratoires et comportementales. Nous montrons qu'un protocole voisin de celui utilis\'e dans ce
projet ne se termine pas. Cela entra\^ine que le protocole originel ne se termine pas non plus. Aussi proposons nous une
modification qui fournit la terminaison. Nous prouvons la correction de ce protocole modifi\'e et nous analysons sa complexit\'e
en temps au pire, dans le mod\'ele des protocoles de population avec temps de couverture. La comparaison de cette complexit\'e
avec celle du protocole optimal est tr\'es d\'efavorable.
Le protocole de collecte de donn\'ees de ZebraNet a fait l'objet de simulations, mais c'est la premi\'ere fois, \'a notre connaissance,
qu'est r\'ealis\'ee une \'etude purement analytique.},
url = {http://hal.inria.fr/inria00586503/fr/},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
xpays = {RU},
sorte = "confnat"
}

F. Becker,
M. Matamala,
N. Nisse,
I. Rapaport,
K. Suchan,
and I. Todinca.
Adding a referee to an interconnection network: What can(not) be computed in one round.
In 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS),
pages 508514,
2011.
IEEE.
[WWW
] [PDF
]
Abstract: 
{In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes which only knows its own ID and the IDs of its neighbors is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3? cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded
degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs. },
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays = {CL},
sorte = "confint",

@inproceedings{BMN+11,
author = {Becker, F. and Matamala, M. and Nisse, N. and Rapaport, I. and Suchan, K. and Todinca, I.},
title = {Adding a referee to an interconnection network: What can(not) be computed in one round},
booktitle = {25th IEEE International Parallel \& Distributed Processing Symposium (IPDPS)},
pages = {508514},
year = {2011},
publisher = {IEEE},
url = {http://arxiv.org/abs/1009.4447},
pdf = {http://arxiv.org/pdf/1009.4447v2},
abstract = {In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes which only knows its own ID and the IDs of its neighbors is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3? cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded
degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs. },
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays = {CL},
sorte = "confint",
}

F. Becker,
M. Matamala,
N. Nisse,
I. Rapaport,
K. Suchan,
and I. Todinca.
Reconstruire un graphe en une ronde.
In Ducourthial,
Bertrand et Felber,
and Pascal, editors,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
]
Abstract: 
{Nous Ã©tudions quelles propriÃ©tÃ©s d'un rÃ©seau peuvent Ãªtre calculÃ©es Ã partir d'une petite quantitÃ© d'informations locales fournie par ses noeuds. Notre modÃ¨le est une restriction de CONGEST, un modÃ¨le distribuÃ© classique. Il est proche du modÃ¨le de complexitÃ© de communication avec messages simultanÃ©s de Babai et al. Chacun des n noeuds qui ne connaissent que leur identifiant, ceux de leurs voisins et la taille du graphe envoie un message de taille O(log(n)) bits Ã une entitÃ© centrale, le superviseur. Celuici doit alors dÃ©terminer une certaine propriÃ©tÃ© du rÃ©seau. Nous montrons que des questions telles que: ''Estce que le graphe contient un triangle? un carrÃ© ? Quel est son diamÃ¨tre?" ne peuvent pas Ãªtre rÃ©solues dans ce modÃ¨le. En revanche, pour de nombreuses classes de graphes : celles de dÃ©gÃ©nÃ©rescence bornÃ©e (incluant les graphes planaires, ceux de largeur arborescente bornÃ©e... ), les sommets peuvent succinctement donner une description complÃ¨te du graphe au superviseur. Nous laissons
ouverte la question de dÃ©cider la connexitÃ©.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
xpays= {CL},
sorte = "confnat",

@inproceedings{BMN+11b,
author = {Becker, F. and Matamala, M. and Nisse, N. and Rapaport, I. and Suchan, K. and Todinca, I.},
title = {{Reconstruire un graphe en une ronde}},
booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2011},
editor = {Ducourthial and Bertrand et Felber and Pascal},
address = {Cap Est\'erel, France},
url = {http://hal.inria.fr/inria00587250/en},
abstract = {Nous Ã©tudions quelles propriÃ©tÃ©s d'un rÃ©seau peuvent Ãªtre calculÃ©es Ã partir d'une petite quantitÃ© d'informations locales fournie par ses noeuds. Notre modÃ¨le est une restriction de CONGEST, un modÃ¨le distribuÃ© classique. Il est proche du modÃ¨le de complexitÃ© de communication avec messages simultanÃ©s de Babai et al. Chacun des n noeuds qui ne connaissent que leur identifiant, ceux de leurs voisins et la taille du graphe envoie un message de taille O(log(n)) bits Ã une entitÃ© centrale, le superviseur. Celuici doit alors dÃ©terminer une certaine propriÃ©tÃ© du rÃ©seau. Nous montrons que des questions telles que: ''Estce que le graphe contient un triangle? un carrÃ© ? Quel est son diamÃ¨tre?" ne peuvent pas Ãªtre rÃ©solues dans ce modÃ¨le. En revanche, pour de nombreuses classes de graphes : celles de dÃ©gÃ©nÃ©rescence bornÃ©e (incluant les graphes planaires, ceux de largeur arborescente bornÃ©e... ), les sommets peuvent succinctement donner une description complÃ¨te du graphe au superviseur. Nous laissons
ouverte la question de dÃ©cider la connexitÃ©.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
xpays= {CL},
sorte = "confnat",
}

S. Belhareth,
D. Coudert,
D. Mazauric,
N. Nisse,
and I. Tahiri.
Reconfiguration avec contraintes physiques dans les réseaux WDM.
In Ducourthial et Bertrand et Felber et Pascal, editor,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
] [PDF
]
Abstract: 
Dans un rÃ©seau WDM, utiliser une nouvelle longueur d'onde dans une ï¬bre demande Ã recalibrer les autres longueurs d'ondes. Cela gÃ©nÃ¨re un coÃ»t (e.g., Ã©nergÃ©tique) qui dÃ©pend non linÃ©airement du nombre de longueurs d'ondes utilisant la ï¬bre. Lorsqu'un ensemble de requÃªtes doivent changer de chemins optiques dans le rÃ©seau (lors d'une opÃ©ration de maintenance sur un lien du rÃ©seau), l'ordre dans lequel les requÃªtes sont dÃ©placÃ©es inï¬ue sur le coÃ»t total de l'opÃ©ration. Nous initions l'Ã©tude du problÃ¨me d'optimisation correspondant. Nous prouvons que dÃ©terminer l'ordre de dÃ©placements optimal est NPcomplet pour un rÃ©seau de 2 nÅuds. Nous donnons des bornes gÃ©nÃ©rales et identiï¬ons des classes d'instances faciles. Enï¬n, nous proposons et Ã©valuons par simulations des heuristiques pour ce problÃ¨me. 
@inproceedings{BCM+11,
author = {Belhareth, S. and Coudert, D. and Mazauric, D. and Nisse, N. and Tahiri, I.},
title = {{Reconfiguration avec contraintes physiques dans les r\'eseaux WDM}},
booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2011},
editor = {Ducourthial et Bertrand et Felber et Pascal},
address = {Cap Est\'erel, France},
pdf = {http://hal.inria.fr/docs/00/58/77/09/PDF/reconf20110406.pdf},
url = {http://hal.inria.fr/inria00583829/en},
abstract = {Dans un rÃ©seau WDM, utiliser une nouvelle longueur d'onde dans une ï¬bre demande Ã recalibrer les autres longueurs d'ondes. Cela gÃ©nÃ¨re un coÃ»t (e.g., Ã©nergÃ©tique) qui dÃ©pend non linÃ©airement du nombre de longueurs d'ondes utilisant la ï¬bre. Lorsqu'un ensemble de requÃªtes doivent changer de chemins optiques dans le rÃ©seau (lors d'une opÃ©ration de maintenance sur un lien du rÃ©seau), l'ordre dans lequel les requÃªtes sont dÃ©placÃ©es inï¬ue sur le coÃ»t total de l'opÃ©ration. Nous initions l'Ã©tude du problÃ¨me d'optimisation correspondant. Nous prouvons que dÃ©terminer l'ordre de dÃ©placements optimal est NPcomplet pour un rÃ©seau de 2 nÅuds. Nous donnons des bornes gÃ©nÃ©rales et identiï¬ons des classes d'instances faciles. Enï¬n, nous proposons et Ã©valuons par simulations des heuristiques pour ce problÃ¨me.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
xpays = {TN},
sorte = "confnat",
}

JC. Bermond,
L. Gargano,
S. Pérennes and
A.A. Rescigno,
and U. Vaccaro.
Optimal Time Data Gathering in Wireless Networks
with OmniDirectional Antennas.
In SIROCCO 2011,
volume 6796 of Lecture Notes in Computer Science,
Gdansk, Poland,
pages 306317,
June 2011.
SpringerVerlag.
[PDF
]
Abstract: 
We study algorithmic and complexity issues originating from
the problem of data gathering
in wireless networks.
We give an algorithm to construct
minimum makespan transmission schedules
for data gathering
when the communication graph
$G$ is a tree network, the interference range is \emph{any}
integer $m\geq 2$, and no buffering is allowed at intermediate nodes.
In the interesting case in which all nodes in the network have to deliver
an arbitrary nonzero number of packets,
we provide a closed formula for the
makespan of the optimal gathering schedule.
Additionally, we consider the problem of determining the
computational complexity of data gathering in general graphs
and show that the problem is weakly NPcomplete. On the positive side,
we design
a simple $(1+2/m)$ factor approximation algorithm for general networks. 
@inproceedings{BGP+11,
author= {JC. Bermond and L. Gargano and S. P\'erennes and
A.A. Rescigno and U. Vaccaro},
title= {Optimal Time Data Gathering in Wireless Networks
with OmniDirectional Antennas },
booktitle= { SIROCCO 2011 },
publisher= { SpringerVerlag },
series= {Lecture Notes in Computer Science},
address= {Gdansk, Poland },
month=jun,
volume = {6796},
pages = {306317},
year= {2011},
PDF={ftp://ftpsop.inria.fr/mascotte/personnel/JeanClaude.Bermond/PUBLIS/BGPRV11.pdf},
abstract={We study algorithmic and complexity issues originating from
the problem of data gathering
in wireless networks.
We give an algorithm to construct
minimum makespan transmission schedules
for data gathering
when the communication graph
$G$ is a tree network, the interference range is \emph{any}
integer $m\geq 2$, and no buffering is allowed at intermediate nodes.
In the interesting case in which all nodes in the network have to deliver
an arbitrary nonzero number of packets,
we provide a closed formula for the
makespan of the optimal gathering schedule.
Additionally, we consider the problem of determining the
computational complexity of data gathering in general graphs
and show that the problem is weakly NPcomplete. On the positive side,
we design
a simple $(1+2/m)$ factor approximation algorithm for general networks.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
xpays = {IT},
}

C. Caillouet and A. Koster.
Routage et Ordonnancement Robustes dans les Réseaux Radio Maillés.
In Ducourthial,
Bertrand et Felber,
and Pascal, editors,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
]
@inproceedings{CaKo11,
author = {C. Caillouet and A. Koster},
title = {{Routage et Ordonnancement Robustes dans les R{\'e}seaux Radio Maill{\'e}s}},
booktitle = {{13es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)}},
year = {2011},
editor = {Ducourthial and Bertrand et Felber and Pascal},
address = {Cap Est{\'e}rel, France},
url = {http://hal.inria.fr/inria00586698/en},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
sorte = "confnat",
}

C. Caillouet,
X. Li,
and T. Razafindralambo.
A Multiobjective Approach for Data Collection in Wireless Sensor Networks.
In 10th International Conference on Ad Hoc Networks and Wireless (AdHocNow),
Padderborn, Germany,
July 2011.
[WWW
]
@inproceedings{CLR11,
author = {C. Caillouet and X. Li and T. Razafindralambo},
title = {{A Multiobjective Approach for Data Collection in Wireless Sensor Networks}},
booktitle = {{10th International Conference on Ad Hoc Networks and Wireless (AdHocNow)}},
year = {2011},
month = Jul,
address = {Padderborn, Germany},
url = {http://hal.inria.fr/inria00601679/en},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

C. Caillouet and T. Razafindralambo.
Compromis énergiedélai pour la collecte de données dans les réseaux de capteurs.
In Ducourthial,
Bertrand et Felber,
and Pascal, editors,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
]
@inproceedings{CaRa11,
author = {C. Caillouet and T. Razafindralambo},
title = {{Compromis {\'e}nergied{\'e}lai pour la collecte de donn{\'e}es dans les r{\'e}seaux de capteurs}},
booktitle = {{13es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)}},
year = {2011},
editor = {Ducourthial and Bertrand et Felber and Pascal},
address = {Cap Est{\'e}rel, France},
url = {http://hal.inria.fr/inria00586681/en},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
sorte = "confnat",
}

V. Campos,
C. Linhares Sales,
A. K. Maia,
N. Martins,
and R. Sampaio.
Restricted coloring problems on graphs with few $P_4$'s.
In VI LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS'11),
volume 37 of Electronic Notes in Discrete Mathematics,
pages 5762,
2011.
[WWW
] [PDF
]
Abstract: 
In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious
chromatic number of $P_4$ tidy graphs and $(q , q â 4)$graphs, for every fixed q. These classes include cographs, $P_4$ sparse and $P_4$ lite graphs. We also
obtain a polynomial time algorithm to determine the Grundy number of $(q , q â 4)$graphs. All these coloring problems are known to be NPhard for general
graphs. 
@InProceedings{CLM+11,
author = {Campos, V. and Linhares Sales, C. and Maia, A. K. and Martins, N. and Sampaio, R.},
title = {Restricted coloring problems on graphs with few $P_4$'s},
OPTcrossref = {},
OPTkey = {},
booktitle = {VI LatinAmerican Algorithms, Graphs and Optimization Symposium (LAGOS'11)},
pages = {5762},
year = {2011},
OPTeditor = {},
volume = {37},
OPTnumber = {},
series = {Electronic Notes in Discrete Mathematics},
OPTaddress = {},
OPTmonth = {},
OPTorganization = {},
OPTpublisher = {},
abstract = {In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious
chromatic number of $P_4$ tidy graphs and $(q , q â 4)$graphs, for every fixed q. These classes include cographs, $P_4$ sparse and $P_4$ lite graphs. We also
obtain a polynomial time algorithm to determine the Grundy number of $(q , q â 4)$graphs. All these coloring problems are known to be NPhard for general
graphs.},
pdf = {http://hal.inria.fr/docs/00/64/31/80/PDF/colfewP4.pdf},
doi = "10.1016/j.endm.2011.05.011",
url = "http://www.sciencedirect.com/science/article/pii/S1571065311000126",
xeditorialboard = {yes},
xproceedings = {yes},
xinternationalaudience = {yes},
xpays = {BR},
sorte = "confint",
}

G. Classen,
D. Coudert,
A. Koster,
and N. Nepomuceno.
A ChanceConstrained Model & Cutting Planes for Fixed Broadband Wireless Networks.
In International Network Optimization Conference (INOC),
volume 6701 of Lecture Notes in Computer Science,
Hamburg, Germany,
pages 3742,
June 2011.
[PDF
]
Abstract: 
In this paper, we propose a chanceconstrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by~$42$\,\27775643230n average. 
@InProceedings{CCKN11b,
author = {G. Cla{\ss}en and D. Coudert and A. Koster and N. Nepomuceno},
title = {A ChanceConstrained Model \& Cutting Planes for Fixed Broadband Wireless Networks},
booktitle = {International Network Optimization Conference (INOC)},
pages = {3742},
year = {2011},
volume = {6701},
series = {Lecture Notes in Computer Science},
address = {Hamburg, Germany},
month = jun,
abstract = {In this paper, we propose a chanceconstrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by~$42$\,\27775643230n average.},
pdf = {http://hal.inria.fr/docs/00/58/76/69/PDF/ClCoKoNenoformat.pdf},
DOI = {10.1007/9783642215278\_5},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={DE,DK},
sorte = "confint",
}

G. Classen,
D. Coudert,
A. Koster,
and N. Nepomuceno.
Bandwidth assignment for reliable fixed broadband wireless networks.
In 12th IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM),
Lucca, Italy,
pages 16,
June 2011.
IEEE.
[PDF
]
Abstract: 
In this paper, we investigate on conceiving reliable fixed broadband wireless networks under outage probability constraints. We introduce a joint optimization of data routing and bandwidth assignment that minimizes the total renewal fees of licenses, while handling all the traffic requirements simultaneously. This problem differs from classical capacity planning in the sense that the capacity of microwave radio links are prone to variations due to external factors (e.g., weather). Therefore, we must consider probabilistic constraints to deal with random parameters (viz., modulation schemes) and guarantee a desirable reliability level of the solution. We propose a (joint) chanceconstrained programming approach to tackle this problem. This approach remains one of the main challenges of modern stochastic programming and it is still considered as very difficult and widely intractable. We then derive integer linear programming (ILP) counterparts for these chanceconstrained programs and propose
cutsetbased valid inequalities to enhance the performance of ILP solvers. Preliminary computational results illustrate the price of reliability and present a comparative study on the performance of the different formulations. 
@InProceedings{CCKN11,
author = {G. Cla{\ss}en and D. Coudert and A. Koster and N. Nepomuceno},
title = {Bandwidth assignment for reliable fixed broadband wireless networks},
booktitle = {12th {IEEE} International Symposium on a World of Wireless Mobile and Multimedia Networks ({WoWMoM})},
pages = {16},
year = {2011},
address = {Lucca, Italy},
month = jun,
publisher = {IEEE},
abstract = {In this paper, we investigate on conceiving reliable fixed broadband wireless networks under outage probability constraints. We introduce a joint optimization of data routing and bandwidth assignment that minimizes the total renewal fees of licenses, while handling all the traffic requirements simultaneously. This problem differs from classical capacity planning in the sense that the capacity of microwave radio links are prone to variations due to external factors (e.g., weather). Therefore, we must consider probabilistic constraints to deal with random parameters (viz., modulation schemes) and guarantee a desirable reliability level of the solution. We propose a (joint) chanceconstrained programming approach to tackle this problem. This approach remains one of the main challenges of modern stochastic programming and it is still considered as very difficult and widely intractable. We then derive integer linear programming (ILP) counterparts for these chanceconstrained programs and propose
cutsetbased valid inequalities to enhance the performance of ILP solvers. Preliminary computational results illustrate the price of reliability and present a comparative study on the performance of the different formulations.},
pdf = {http://hal.inria.fr/docs/00/58/76/98/PDF/bare_confnoformat.pdf},
DOI = {10.1109/WoWMoM.2011.5986471},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={DE,DK},
sorte = "confint",
}

D. Coudert,
N. Nepomuceno,
and I. Tahiri.
Energy saving in fixed wireless broadband networks.
In International Network Optimization Conference (INOC),
volume 6701 of Lecture Notes in Computer Science,
Hamburg, Germany,
pages 484489,
June 2011.
[PDF
]
Abstract: 
In this paper, we present a mathematical formulation for saving energy in fixed broadband wireless networks by selectively turning off idle communication devices in lowdemand scenarios. This problem relies on a fixedcharge capacitated network design (FCCND), which is very hard to optimize. We then propose heuristic algorithms to produce feasible solutions in a short time. 
@InProceedings{CNT11b,
author = {Coudert, D. and Nepomuceno, N. and Tahiri, I.},
title = {Energy saving in fixed wireless broadband networks},
booktitle = {International Network Optimization Conference (INOC)},
pages = {484489},
year = {2011},
volume = {6701},
series = {Lecture Notes in Computer Science},
address = {Hamburg, Germany},
month = jun,
abstract = {In this paper, we present a mathematical formulation for saving energy in fixed broadband wireless networks by selectively turning off idle communication devices in lowdemand scenarios. This problem relies on a fixedcharge capacitated network design (FCCND), which is very hard to optimize. We then propose heuristic algorithms to produce feasible solutions in a short time.},
pdf = {http://hal.inria.fr/docs/00/58/76/85/PDF/CNT11noformat.pdf},
DOI = {10.1007/9783642215278\_53},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={DK},
sorte = "confint",
}

D. Coudert,
N. Nepomuceno,
and I. Tahiri.
Optimisation de la consommation énergétique dans les réseaux sans fil fixes.
In Pascal Ducourthial, Bertrand et Felber, editor,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel France,
2011.
[WWW
] [PDF
]
Abstract: 
{N}ous {\'e}tudions le probl{\`e}me d'optimisation {\'e}nerg{\'e}tique dans les r{\'e}seaux sans fil fixes dans le cas d'une faible demande de trafic par rapport {\`a} la capacit{\'e} du r{\'e}seau. {N}ous proposons un programme lin{\'e}aire pour r{\'e}soudre le probl{\`e}me, puis nous pr{\'e}sentons une heuristique permettant de trouver rapidement une bonne solution. 
@inproceedings{CNT11,
HAL_ID = {inria00588129},
url = {http://hal.inria.fr/inria00588129/en/},
title = { {O}ptimisation de la consommation {\'e}nerg{\'e}tique dans les r{\'e}seaux sans fil fixes},
author = {Coudert, D. and Nepomuceno, N. and Tahiri, I.},
abstract = {{N}ous {\'e}tudions le probl{\`e}me d'optimisation {\'e}nerg{\'e}tique dans les r{\'e}seaux sans fil fixes dans le cas d'une faible demande de trafic par rapport {\`a} la capacit{\'e} du r{\'e}seau. {N}ous proposons un programme lin{\'e}aire pour r{\'e}soudre le probl{\`e}me, puis nous pr{\'e}sentons une heuristique permettant de trouver rapidement une bonne solution.},
language = {{F}ran{\c{c}}ais},
affiliation = {{MASCOTTE}  {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S}  {INRIA}  {U}niversit{\'e} de {N}ice {S}ophia{A}ntipolis  {CNRS} : {UMR}6070 },
booktitle = {13es {R}encontres {F}rancophones sur les {A}spects {A}lgorithmiques de {T}{\'e}l{\'e}communications ({A}lgo{T}el) },
address = {{C}ap {E}st{\'e}rel {F}rance },
editor = {{D}ucourthial, {B}ertrand et {F}elber, {P}ascal },
audience = {internationale },
year = {2011},
pdf = {http://hal.inria.fr/inria00588129/PDF/document.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
sorte = "confnat",
}

G. D'Angelo,
Mattia D'Emidio,
Daniele Frigioni,
and Vinicio Maurizio.
A SpeedUp Technique for Distributed Shortest Paths Computation.
In Beniamino Murgante,
Osvaldo Gervasi,
Andrés Iglesias,
David Taniar,
and Bernady O. Apduhan, editors,
11th International Conference on Computational Science and Its Applications (ICCSA 2011),
volume 6783 of Lecture Notes in Computer Science,
Santander, Spain,
pages 578593,
June 2011.
Springer.
[WWW
] [PDF
]
Abstract: 
We propose a simple and practical speedup technique, which can be combined with every distance vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm. We combine the new technique with two algorithms known in the literature: DUAL, which is part of CISCO's widely used EIGRP protocol, and the recent DUST, which has been shown to be very effective on networks with power law node degree distribution. We give experimental evidence that these combinations lead to an important gain in terms of the number of messages sent by DUAL and DUST at the price of a little increase in terms of space occupancy per node. 
@inproceedings{DDF+11,
hal_id = {hal00644049},
url = {http://hal.inria.fr/hal00644049/en/},
title = {{A SpeedUp Technique for Distributed Shortest Paths Computation}},
author = {G. D'Angelo and D'Emidio, Mattia and Frigioni, Daniele and Maurizio, Vinicio},
abstract = {{We propose a simple and practical speedup technique, which can be combined with every distance vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm. We combine the new technique with two algorithms known in the literature: DUAL, which is part of CISCO's widely used EIGRP protocol, and the recent DUST, which has been shown to be very effective on networks with power law node degree distribution. We give experimental evidence that these combinations lead to an important gain in terms of the number of messages sent by DUAL and DUST at the price of a little increase in terms of space occupancy per node.}},
language = {English},
booktitle = {{11th International Conference on Computational Science and Its Applications (ICCSA 2011)}},
publisher = {Springer},
pages = {578593},
address = {Santander, Spain},
volume = {6783},
editor = {Beniamino Murgante and Osvaldo Gervasi and Andr{\'e}s Iglesias and David Taniar and Bernady O. Apduhan },
series = {Lecture Notes in Computer Science },
audience = {international },
doi = {10.1007/9783642218873\_44 },
year = {2011},
month = Jun,
pdf = {http://hal.inria.fr/hal00644049/PDF/dlp.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

G. D'Angelo,
Gabriele Di Stefano,
and Alfredo Navarra.
Bandwidth Constrained Multiinterface Networks.
In Ivana Cerná,
Tibor Gyimóthy,
Juraj Hromkovic,
Keith Jefferey,
Rastislav Královic,
Marko Vukolic,
and Stefan Wolf, editors,
37th Conference on Current Trends in Theory and Practice of Computer Science,
volume 6543 of Lecture Notes in Computer Science,
Novy Smokovec, Slovakia,
pages 202213,
January 2011.
Springer.
[WWW
] [PDF
]
Abstract: 
In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider the problem of activating the cheapest set of interfaces among a network Gâ=â(V,E) in order to guarantee a minimum bandwidth B of communication between two specified nodes. Nodes V represent the devices, edges E represent the connections that can be established. In practical cases, a bounded number k of different interfaces among all the devices can be considered. Despite this assumption, the problem turns out to be NPhard even for small values of k and $\Delta$, where $\Delta$ is the maximum degree of the network. In particular, the problem is NPhard for
any fixed kâ$\ge$â2 and $\Delta$â$\ge$â3, while it is polynomially solvable when kâ=â1, or $\Delta$â$\le$â2 and kâ=âO(1). Moreover, we show that the problem is not approximable within $\eta$logB or $\Omega$(loglogV) for any fixed kâ$\ge$â3, $\Delta$â$\ge$â3, and for a certain constant $\eta$, unless P=NP. We then provide an approximation algorithm with ratio guarantee of b max , where b max is the maximum communication bandwidth allowed among all the available interfaces. Finally, we focus on particular cases by providing complexity results and polynomial algorithms for $\Delta$â$\le$â2. 
@inproceedings{DDN11e,
hal_id = {hal00644104},
url = {http://hal.inria.fr/hal00644104/en/},
title = {{Bandwidth Constrained Multiinterface Networks}},
author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},
abstract = {{In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider the problem of activating the cheapest set of interfaces among a network Gâ=â(V,E) in order to guarantee a minimum bandwidth B of communication between two specified nodes. Nodes V represent the devices, edges E represent the connections that can be established. In practical cases, a bounded number k of different interfaces among all the devices can be considered. Despite this assumption, the problem turns out to be NPhard even for small values of k and $\Delta$, where $\Delta$ is the maximum degree of the network. In particular, the problem is NPhard for
any fixed kâ$\ge$â2 and $\Delta$â$\ge$â3, while it is polynomially solvable when kâ=â1, or $\Delta$â$\le$â2 and kâ=âO(1). Moreover, we show that the problem is not approximable within $\eta$logB or $\Omega$(loglogV) for any fixed kâ$\ge$â3, $\Delta$â$\ge$â3, and for a certain constant $\eta$, unless P=NP. We then provide an approximation algorithm with ratio guarantee of b max , where b max is the maximum communication bandwidth allowed among all the available interfaces. Finally, we focus on particular cases by providing complexity results and polynomial algorithms for $\Delta$â$\le$â2.}},
language = {English},
booktitle = {{37th Conference on Current Trends in Theory and Practice of Computer Science}},
publisher = {Springer},
pages = {202213},
address = {Nov{\'y} Smokovec, Slovakia},
volume = {6543},
editor = {Ivana Cern{\'a} and Tibor Gyim{\'o}thy and Juraj Hromkovic and Keith Jefferey and Rastislav Kr{\'a}lovic and Marko Vukolic and Stefan Wolf },
series = {Lecture Notes in Computer Science },
doi = {10.1007/9783642183812\_17 },
year = {2011},
month = Jan,
pdf = {http://hal.inria.fr/hal00644104/PDF/MultiInterfacesFlowTheor.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

G. D'Angelo,
Gabriele Di Stefano,
and Alfredo Navarra.
Gathering of Six Robots on Anonymous Symmetric Rings.
In Adrian Kosowski and Masafumi Yamashita, editors,
Structural Information and Communication Complexity,
volume 6796 of Lecture Notes in Computer Science,
Gdansk, Poland,
pages 174185,
July 2011.
Springer.
[WWW
] [PDF
]
Abstract: 
The paper deals with a recent model of robotbased computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in LookComputeMove cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In particular, we consider the case of only six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one single node. This is in fact the first case left open after a series of papers [1,2,3,4] dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that
guarantees a positive answer to the posed question. Despite the very special case considered, the provided strategy turns out to be very interesting as it neither completely falls into symmetrybreaking nor into symmetrypreserving techniques. 
@inproceedings{DDN11b,
hal_id = {hal00644039},
url = {http://hal.inria.fr/hal00644039/en/},
title = {{Gathering of Six Robots on Anonymous Symmetric Rings}},
author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},
abstract = {{The paper deals with a recent model of robotbased computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in LookComputeMove cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In particular, we consider the case of only six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one single node. This is in fact the first case left open after a series of papers [1,2,3,4] dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that
guarantees a positive answer to the posed question. Despite the very special case considered, the provided strategy turns out to be very interesting as it neither completely falls into symmetrybreaking nor into symmetrypreserving techniques.}},
language = {English},
booktitle = {{Structural Information and Communication Complexity}},
publisher = {Springer},
pages = {174185},
address = {Gdansk, Poland},
volume = {6796},
editor = {Adrian Kosowski and Masafumi Yamashita },
series = {Lecture Notes in Computer Science },
doi = {10.1007/9783642222122\_16 },
year = {2011},
month = Jul,
pdf = {http://hal.inria.fr/hal00644039/PDF/GatheringSixRobots.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

G. D'Angelo,
Gabriele Di Stefano,
and Alfredo Navarra.
Maximum Flow and MinimumCost Flow in MultiInterface Networks.
In 5th International Conference on Ubiquitous Information Management and Communication,
Seoul, Korea, Republic Of,
pages 19,
February 2011.
ACM.
[WWW
] [PDF
]
Abstract: 
In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider two fundamental optimization problems. In the first one, we aim to activate a set of interfaces in the network G = (V, E) in order to guarantee the maximal bandwidth between two given nodes. Nodes V represent the devices, edges E represent the connections that can be established according to the availability of the interfaces in the devices. In the second problem, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that the first problem is
polynomially solvable while the second one is NPHard. However, we experimentally analyzed an algorithm for the second problem, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in realworld networks. 
@inproceedings{DDN11d,
hal_id = {hal00644073},
url = {http://hal.inria.fr/hal00644073/en/},
title = {{Maximum Flow and MinimumCost Flow in MultiInterface Networks}},
author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},
abstract = {{In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider two fundamental optimization problems. In the first one, we aim to activate a set of interfaces in the network G = (V, E) in order to guarantee the maximal bandwidth between two given nodes. Nodes V represent the devices, edges E represent the connections that can be established according to the availability of the interfaces in the devices. In the second problem, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that the first problem is
polynomially solvable while the second one is NPHard. However, we experimentally analyzed an algorithm for the second problem, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in realworld networks.}},
language = {English},
booktitle = {{5th International Conference on Ubiquitous Information Management and Communication}},
publisher = {ACM},
pages = {19},
address = {Seoul, Korea, Republic Of},
doi = {10.1145/1968613.1968637 },
year = {2011},
month = Feb,
pdf = {http://hal.inria.fr/hal00644073/PDF/MultiInterfacesFlowExp.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

G. D'Angelo,
Gabriele Di Stefano,
and Alfredo Navarra.
MinMax Coverage in Multiinterface Networks.
In Ivana Cerná,
Tibor Gyimóthy,
Juraj Hromkovic,
Keith Jefferey,
Rastislav Královic,
Marko Vukolic,
and Stefan Wolf, editors,
37th Conference on Current Trends in Theory and Practice of Computer Science,
volume 6543 of Lecture Notes in Computer Science,
Novy Smokovec, Slovakia,
pages 190201,
January 2011.
Springer.
[WWW
] [PDF
]
Abstract: 
We consider devices equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of establishing the connections defined by a network Gâ=â(V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that must be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges. We prove that the problem is NPhard for any fixed $\Delta$â$\ge$â5 and kâ$\ge$â16, with $\Delta$ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be
approximated within $\Omega$(ln $\Delta$). We then provide a general approximation algorithm which guarantees a factor of O((1â+âb)ln ($\Delta$)), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. 
@inproceedings{DDN11f,
hal_id = {hal00644084},
url = {http://hal.inria.fr/hal00644084/en/},
title = {{MinMax Coverage in Multiinterface Networks}},
author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},
abstract = {{We consider devices equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of establishing the connections defined by a network Gâ=â(V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that must be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges. We prove that the problem is NPhard for any fixed $\Delta$â$\ge$â5 and kâ$\ge$â16, with $\Delta$ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be
approximated within $\Omega$(ln $\Delta$). We then provide a general approximation algorithm which guarantees a factor of O((1â+âb)ln ($\Delta$)), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented.}},
language = {English},
booktitle = {{37th Conference on Current Trends in Theory and Practice of Computer Science}},
publisher = {Springer},
pages = {190201},
address = {Nov{\'y} Smokovec, Slovakia},
volume = {6543},
editor = {Ivana Cern{\'a} and Tibor Gyim{\'o}thy and Juraj Hromkovic and Keith Jefferey and Rastislav Kr{\'a}lovic and Marko Vukolic and Stefan Wolf },
series = {Lecture Notes in Computer Science },
audience = {international },
doi = {10.1007/9783642183812\_16 },
year = {2011},
month = Jan,
pdf = {http://hal.inria.fr/hal00644084/PDF/MultiInterfacesCoverage.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

G. D'Angelo,
Daniele Frigioni,
and Camillo Vitale.
Dynamic ArcFlags in Road Networks.
In Panos M. Pardalos and Steffen Rebennack, editors,
10th International Symposium, SEA 2011,
volume 6630 of Lecture Notes in Computer Science,
Kolimpari, Chania, Crete, Greece,
pages 8899,
April 2011.
Springer.
[WWW
] [PDF
]
Abstract: 
In this work we introduce a new data structure, named RoadSigns, which allows us to efficiently update the ArcFlags of a graph in a dynamic scenario. RoadSigns can be used to compute ArcFlags, can be efficiently updated and do not require large space consumption for many realworld graphs like, e.g., graphs arising from road networks. In detail, we define an algorithm to preprocess RoadSigns and an algorithm to update them each time that a weight increase operation occurs on an edge of the network. We also experimentally analyze the proposed algorithms in realworld road networks showing that they yields a significant speedup in the updating phase of ArcFlags, at the cost of a very small space and time overhead in the preprocessing phase. 
@inproceedings{DDV11c,
hal_id = {hal00644054},
url = {http://hal.inria.fr/hal00644054/en/},
title = {{Dynamic ArcFlags in Road Networks}},
author = {G. D'Angelo and Frigioni, Daniele and Vitale, Camillo},
abstract = {{In this work we introduce a new data structure, named RoadSigns, which allows us to efficiently update the ArcFlags of a graph in a dynamic scenario. RoadSigns can be used to compute ArcFlags, can be efficiently updated and do not require large space consumption for many realworld graphs like, e.g., graphs arising from road networks. In detail, we define an algorithm to preprocess RoadSigns and an algorithm to update them each time that a weight increase operation occurs on an edge of the network. We also experimentally analyze the proposed algorithms in realworld road networks showing that they yields a significant speedup in the updating phase of ArcFlags, at the cost of a very small space and time overhead in the preprocessing phase.}},
language = {English},
booktitle = {{10th International Symposium, SEA 2011}},
publisher = {Springer},
pages = {8899},
address = {Kolimpari, Chania, Crete, Greece},
volume = {6630},
editor = {Panos M. Pardalos and Steffen Rebennack },
series = {Lecture Notes in Computer Science },
doi = {10.1007/9783642206627\_8 },
year = {2011},
month = Apr,
pdf = {http://hal.inria.fr/hal00644054/PDF/RoadSigns.pdf},
xpays = {IT},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

O. Dalle and E. Mancini.
Traces Generation To Simulate LargeScale Distributed Applications.
In S. Jain,
R. R. Creasey,
J. Himmelspach,
K. P. White,
and M. Fu, editors,
Winter Simulation Conference,
Phoenix, AZ, ÉtatsUnis,
pages 10p.,
December 2011.
[WWW
] [PDF
]
Abstract: 
In order to study the performance of scheduling algorithms, simulators of parallel and distributed applications need accurate models of the application's behavior during execution.
For this purpose, traces of lowlevel events collected during the actual execution of real applications are needed.
Collecting such traces is a difficult task due to the timing, to the interference of instrumentation code, and to the storage and transfer of the collected data.
To address this problem we propose a comprehensive software architecture, which instruments the application's executables, gather hierarchically the traces, and postprocess them in order to feed simulation models.
We designed it to be scalable, modular and extensible. 
@inproceedings{DaMa11,
hal_id = {inria00638561},
url = {http://hal.inria.fr/inria00638561},
title = {{Traces Generation To Simulate LargeScale Distributed Applications}},
author = {Dalle, O. and Mancini, E.},
abstract = {{In order to study the performance of scheduling algorithms, simulators of parallel and distributed applications need accurate models of the application's behavior during execution.
For this purpose, traces of lowlevel events collected during the actual execution of real applications are needed.
Collecting such traces is a difficult task due to the timing, to the interference of instrumentation code, and to the storage and transfer of the collected data.
To address this problem we propose a comprehensive software architecture, which instruments the application's executables, gather hierarchically the traces, and postprocess them in order to feed simulation models.
We designed it to be scalable, modular and extensible.}},
booktitle = {{Winter Simulation Conference}},
pages = {10p.},
address = {Phoenix, AZ, {\'E}tatsUnis},
editor = {Jain, S. and Creasey, R. R. and Himmelspach, J. and White, K. P. and Fu, M. },
year = {2011},
month = Dec,
pdf = {http://hal.inria.fr/inria00638561/PDF/MaDa11.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

O. Dalle and J. Ribault.
Some Desired Features for the DEVS Architecture Description Language.
In Proceedings of the Symposium On Theory of Modeling and Simulation  DEVS Integrative M&S Symposium (TMS/DEVS 2011),
volume Book 4  Symposium on Theory of Modeling & Simulation  DEVS Integrative M&S Symposium (TMS/DEVS),
Boston, MA, ÉtatsUnis,
pages 258263,
04 2011.
[WWW
] [PDF
]
Abstract: 
ADL are particularly well suited for componentbased model
frameworks that support hierarchical composition, such as DEVS with coupled
models. In this paper we present some features found in the ADL of another
hierarchical component model, namely the Fractal Component Model (FCM).
To our best knowledge, these features are not yet available in most of the
current DEVS implementations. Using a few examples coming from our experience,
we demonstrate the usefulness of these features for Modeling & Simulation and
their potential relevance for inclusion in a future DEVS implementation
standard. 
@InProceedings{DaRi11,
author = {O. Dalle and J. Ribault},
title = {Some Desired Features for the DEVS Architecture Description Language},
booktitle = {Proceedings of the Symposium On Theory of Modeling and Simulation  DEVS Integrative M\&S Symposium (TMS/DEVS 2011)},
year = {2011},
pages = {258263},
address = {Boston, MA, {\'E}tatsUnis},
volume = {Book 4  Symposium on Theory of Modeling \& Simulation  DEVS Integrative M\&S Symposium (TMS/DEVS)},
month = {04},
url = {http://hal.inria.fr/inria00638565/en/},
pdf = {http://hal.inria.fr/inria00638565/PDF/document.pdf},
abstract = {ADL are particularly well suited for componentbased model
frameworks that support hierarchical composition, such as DEVS with coupled
models. In this paper we present some features found in the ADL of another
hierarchical component model, namely the Fractal Component Model (FCM).
To our best knowledge, these features are not yet available in most of the
current DEVS implementations. Using a few examples coming from our experience,
we demonstrate the usefulness of these features for Modeling & Simulation and
their potential relevance for inclusion in a future DEVS implementation
standard.},
xeditorialboard={yes},
xproceedings={no},
xinternationalaudience={yes},
sorte = "confint",
}

S. Felix and J. Galtier.
Shortest Paths and Probabilities on TimeDependent Graphs  Applications to Transport Networks.
In Proceedings of the 11th International Conference on ITS Telecommunications,
Saint Petersburg, Russia,
pages 5662,
August 2011.
[WWW
]
Abstract: 
In this paper, we focus on timedependent graphs
which seem to be a good way to model transport networks. In
the first part, we remind some notations and techniques related
to timedependent graphs. In the second one, we introduce new
algorithms to take into account the notion of probability related
to paths in order to guarantee travelling times with a certain
accuracy. We also discuss different probabilistic models and show
the links between them. 
@inproceedings{Fe11,
address = {Saint Petersburg, Russia},
author = {S. Felix and J. Galtier},
booktitle = {Proceedings of the 11th International Conference on ITS Telecommunications},
pages = {5662},
month = {August},
title = {Shortest Paths and Probabilities on TimeDependent Graphs  Applications to Transport Networks},
year = 2011,
isbn = {9781605589459},
url={http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=06060121},
abstract = {In this paper, we focus on timedependent graphs
which seem to be a good way to model transport networks. In
the first part, we remind some notations and techniques related
to timedependent graphs. In the second one, we introduce new
algorithms to take into account the notion of probability related
to paths in order to guarantee travelling times with a certain
accuracy. We also discuss different probabilistic models and show
the links between them.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
sorte = "confint",
}

F. Giroire,
D. Mazauric,
and J. Moulierac.
Routage efficace en énergie.
In Ducourthial et Bertrand et Felber et Pascal, editor,
13es Rencontres Francophones sur les Aspects
Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
]
Abstract: 
De rÃ©centes Ã©tudes montrent que la charge de trafic des
routeurs n'a qu'une faible influence sur leur consommation
Ã©nergÃ©tique. Par consÃ©quent, la consommation dans les rÃ©seaux est
fortement liÃ©e au nombre d'Ã©quipements du rÃ©seau activÃ©s (interfaces,
chassis, etc). Dans un objectif de minimisation de l'Ã©nergie dans les
rÃ©seaux, il est intÃ©ressant de minimiser le nombre (pondÃ©rÃ©)
d'Ã©quipements utilisÃ©s lors du routage. Dans cet article, nous
considÃ©rons une architecture simplifiÃ©e oÃ¹ un lien entre deux routeurs
relie deux interfaces. Quand un lien n'est pas activÃ©, les deux
interfaces correspondantes peuvent Ãªtre Ã©teintes. Par consÃ©quent, afin
de rÃ©duire la consommation d'Ã©nergie, l'objectif est de trouver un
routage qui minimise le nombre de liens utilisÃ©s et satisfait toutes
les demandes. Nous montrons des rÃ©sultats d'inapproximabilitÃ© de ce
problÃ¨me, mÃªme si l'on considÃ¨re des instances particuliÃ¨res. Nous
prouvons des bornes en gÃ©nÃ©ral et pour des topologies particuliÃ¨res
telles que la grille, l'arbre ou le graphe complet. Nous proposons
ensuite une heuristique dont nous Ã©valuons les performances Ã l'aide
de simulations sur des topologies rÃ©elles. Nous Ã©tudions ensuite
l'impact de ces solutions efficaces en Ã©nergie sur la tolÃ©rance aux
pannes et sur la longueur moyenne des routes. 
@inproceedings{GMM11,
author = {Giroire, F. and Mazauric, D. and Moulierac, J.},
title = {{Routage efficace en \'energie}},
booktitle = {13es Rencontres Francophones sur les Aspects
Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2011},
editor = {Ducourthial et Bertrand et Felber et Pascal},
address = {Cap Est\'erel, France},
url = {http://hal.inria.fr/inria00587944/fr},
abstract = {De rÃ©centes Ã©tudes montrent que la charge de trafic des
routeurs n'a qu'une faible influence sur leur consommation
Ã©nergÃ©tique. Par consÃ©quent, la consommation dans les rÃ©seaux est
fortement liÃ©e au nombre d'Ã©quipements du rÃ©seau activÃ©s (interfaces,
chassis, etc). Dans un objectif de minimisation de l'Ã©nergie dans les
rÃ©seaux, il est intÃ©ressant de minimiser le nombre (pondÃ©rÃ©)
d'Ã©quipements utilisÃ©s lors du routage. Dans cet article, nous
considÃ©rons une architecture simplifiÃ©e oÃ¹ un lien entre deux routeurs
relie deux interfaces. Quand un lien n'est pas activÃ©, les deux
interfaces correspondantes peuvent Ãªtre Ã©teintes. Par consÃ©quent, afin
de rÃ©duire la consommation d'Ã©nergie, l'objectif est de trouver un
routage qui minimise le nombre de liens utilisÃ©s et satisfait toutes
les demandes. Nous montrons des rÃ©sultats d'inapproximabilitÃ© de ce
problÃ¨me, mÃªme si l'on considÃ¨re des instances particuliÃ¨res. Nous
prouvons des bornes en gÃ©nÃ©ral et pour des topologies particuliÃ¨res
telles que la grille, l'arbre ou le graphe complet. Nous proposons
ensuite une heuristique dont nous Ã©valuons les performances Ã l'aide
de simulations sur des topologies rÃ©elles. Nous Ã©tudions ensuite
l'impact de ces solutions efficaces en Ã©nergie sur la tolÃ©rance aux
pannes et sur la longueur moyenne des routes.},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={no},
xpays = {MA},
sorte = "confnat",
}

Y. Liu and G. Simon.
PeerAssisted Timeshifted Streaming Systems: Design and Promises.
In IEEE International Conference on Communications (ICC'2011),
Kyoto, Japan,
06 2011.
IEEE.
[PDF
]
Abstract: 
Timeshifted streaming (or catchup TV) allows viewers to watch their TV programs within an expanded time window. In this paper, we emphasize the challenging characteristics of timeshifted TV systems that prevent known delivery systems to be used. We model timeshifted TV as multipleinterval graph, then we present a PeerAssisted CatchUp Streaming system, namely PACUS, where a set of end users' computers assists the server for the content delivery. We show in particular how the PACUS tracker server can be efficiently implemented for catchup TV. We demonstrate the benefits of PACUS by simulations. We especially highlight that PACUS reduces the traffic at the server side with the advantages of lightweight and selfadaptive unstructured peertopeer systems. 
@InProceedings{LiSi+11,
author = {Y. Liu and G. Simon},
title = {PeerAssisted Timeshifted Streaming Systems: Design and Promises},
booktitle = {IEEE International Conference on Communications (ICC'2011)},
year = {2011},
address = {Kyoto, Japan},
month = {06},
publisher = {IEEE},
abstract = { Timeshifted streaming (or catchup TV) allows viewers to watch their TV programs within an expanded time window. In this paper, we emphasize the challenging characteristics of timeshifted TV systems that prevent known delivery systems to be used. We model timeshifted TV as multipleinterval graph, then we present a PeerAssisted CatchUp Streaming system, namely PACUS, where a set of end users' computers assists the server for the content delivery. We show in particular how the PACUS tracker server can be efficiently implemented for catchup TV. We demonstrate the benefits of PACUS by simulations. We especially highlight that PACUS reduces the traffic at the server side with the advantages of lightweight and selfadaptive unstructured peertopeer systems.},
pdf = {ftp://ftpsop.inria.fr/mascotte/Publications/LS+11.pdf},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={},
sorte = "confint",
}

F. Maffray and G. Morel.
Algorithmes linÃ©aires pour les graphes sans $P_5$ 3colorables.
In 12e congrès annuel de la ROADEF,
2011.
@inproceedings{MaMo11b,
title = {{ Algorithmes linÃ©aires pour les graphes sans $P_5$ 3colorables}},
author={Maffray, F. and Morel, G.},
booktitle={12e congr\`es annuel de la ROADEF},
year={2011},
xeditorialboard = {no},
xproceedings = {yes},
xinternationalaudience = {no},
sorte = "confnat",
}

P. Aboulker,
F. Havet,
and N. Trotignon.
On wheelfree graphs.
Research Report RR7651,
INRIA,
June 2011.
[WWW
] [PDF
]
Abstract: 
A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3connected graph that does not contain a wheel as a subgraph is in fact minimally 3connected. We prove that every graph that does not contain a wheel as a subgraph is 3colorable. 
@techreport{AHT11,
hal_id= {inria00602079},
url = {http://hal.inria.fr/inria00602079/en/},
title = {{On wheelfree graphs}},
author = {P. Aboulker and F. Havet and N. Trotignon},
abstract = {{A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3connected graph that does not contain a wheel as a subgraph is in fact minimally 3connected. We prove that every graph that does not contain a wheel as a subgraph is 3colorable.}},
language = {Anglais},
affiliation = {Laboratoire d'informatique Algorithmique : Fondements et Applications  LIAFA  CNRS : UMR7089  Universit\'e Paris Diderot  Paris 7  MASCOTTE  INRIA Sophia Antipolis / Laboratoire I3S  INRIA  Universit\'e de Nice SophiaAntipolis  CNRS : UMR6070},
type = {Research Report},
institution = {INRIA},
number = {RR7651},
year = {2011},
month = Jun,
pdf = {http://hal.inria.fr/inria00602079/PDF/RR7651.pdf},
xeditorialboard={no},
xproceedings={yes},
xinternationalaudience={yes},
}

L. AddarioBerry,
F. Havet,
C. Linhares Sales,
B. Reed,
and S. Thomassé.
Oriented trees in digraphs.
Research Report 7502,
INRIA,
01 2011.
[WWW
] [PDF
]
Abstract: 
Let $f(k)$ be the smallest integer such that every $f(k)$chromatic digraph contains every oriented tree of order $k$.
Burr proved that $f(k)\leq (k1)^2$ and conjectured $f(k)=2n2$.
In this paper, we give some sufficient conditions for an $n$chromatic digraphs to contains some oriented tree.
In particular, we show that every acyclic $n$chromatic digraph contains every oriented tree of order $n$.
We also show that $f(k)\leq k^2/2k/2+1$.
Finally, we consider the existence of antidirected trees in digraphs.
We prove that every antidirected tree of order $k$ is contained in every $(5k9)$chromatic digraph.
We conjecture that if $E(D) > (k2) V(D)$,
then the digraph $D$ contains every antidirected tree of order $k$.
This generalizes Burr's conjecture for antidirected trees and the celebrated Erd\H{o}sS\'os Conjecture.
We give some evidences for our conjecture to be true. 
@TechReport{AHL+11,
author = {AddarioBerry, L. and Havet, F. and Linhares Sales, C. and Reed, B. and Thomass\'e, S.},
title = {Oriented trees in digraphs},
year = {2011},
month = {01},
institution = {INRIA},
number = {7502},
type = {Research Report},
URL = {http://hal.inria.fr/inria00551133/fr/},
PDF = {http://hal.inria.fr/docs/00/55/11/33/PDF/RR7502.pdf},
abstract = {Let $f(k)$ be the smallest integer such that every $f(k)$chromatic digraph contains every oriented tree of order $k$.
Burr proved that $f(k)\leq (k1)^2$ and conjectured $f(k)=2n2$.
In this paper, we give some sufficient conditions for an $n$chromatic digraphs to contains some oriented tree.
In particular, we show that every acyclic $n$chromatic digraph contains every oriented tree of order $n$.
We also show that $f(k)\leq k^2/2k/2+1$.
Finally, we consider the existence of antidirected trees in digraphs.
We prove that every antidirected tree of order $k$ is contained in every $(5k9)$chromatic digraph.
We conjecture that if $E(D) > (k2) V(D)$,
then the digraph $D$ contains every antidirected tree of order $k$.
This generalizes Burr's conjecture for antidirected trees and the celebrated Erd\H{o}sS\'os Conjecture.
We give some evidences for our conjecture to be true.},
sorte = {Rapports},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
xpays={BR,CA},
}

J. Araujo,
JC. Bermond,
F. Giroire,
F. Havet,
D. Mazauric,
and R. Modrzejewski.
Weighted Improper Colouring.
Research Report RR7590,
INRIA,
04 2011.
[WWW
] [PDF
]
Keywords:
graph colouring,
improper colouring,
grids,
integer programming,
algorithms.
Abstract: 
{I}n this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. {I}n reallife wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. {W}e model this with a noise matrix. {T}he interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. {T}he problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. {W}e provide several general results, such as bounds on this number of colours (e.g. a {B}rook's like theorem). {W}e then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. {W}e provide the chromatic number of the square, triangular and hexagonal grids for all possible
admissible interference levels. {F}inally, we model the problem using linear programming, propose and test a heuristic and an exact branch\&bound algorithms on random celllike graphs, namely the {P}oisson {V}oronoi tessellations. 
@techreport{ABGH+11a,
url = {http://hal.inria.fr/inria00583036/en/},
title = { {W}eighted {I}mproper {C}olouring},
author = {J. Araujo and JC. Bermond and F. Giroire and F. Havet and D. Mazauric and R. Modrzejewski},
abstract = {{I}n this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. {I}n reallife wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. {W}e model this with a noise matrix. {T}he interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. {T}he problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. {W}e provide several general results, such as bounds on this number of colours (e.g. a {B}rook's like theorem). {W}e then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. {W}e provide the chromatic number of the square, triangular and hexagonal grids for all possible
admissible interference levels. {F}inally, we model the problem using linear programming, propose and test a heuristic and an exact branch\&bound algorithms on random celllike graphs, namely the {P}oisson {V}oronoi tessellations.},
keywords = {graph colouring, improper colouring, grids, integer programming, algorithms},
language = {{A}nglais},
affiliation = {{MASCOTTE}  {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S}  {INRIA}  {U}niversit{\'e} de {N}ice {S}ophia{A}ntipolis  {CNRS} : {UMR}6070  {P}arallelism, {G}raphs and {O}ptimization {R}esearch {G}roup  {P}ar{GO}  {U}niversidade {F}ederal do {C}eara  {MAESTRO}  {INRIA} {S}ophia {A}ntipolis  {INRIA}  {U}niversit{\'e} {M}ontpellier {II}  {S}ciences et {T}echniques du {L}anguedoc },
pages = {16 },
type = {Research Report},
institution = {INRIA},
number = {{RR}7590},
month = {04},
year = {2011},
pdf = {http://hal.inria.fr/inria00583036/PDF/RR7590.pdf},
sorte = {Rapports},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
}

J. Araujo,
V. Campos,
F. Giroire,
N. Nisse,
L. Sampaio,
and R. Soares.
On the hull number of some graph classes.
Technical report RR7567,
INRIA,
September 2011.
[WWW
] [PDF
]
Abstract: 
In this paper, we study the geodetic convexity of graphs focusing on the problem of the complexity to compute inclusionminimum hull set of a graph in several graph classes. For any two vertices $u,v\in V$ of a connected graph $G=(V,E)$, the {\em closed interval} $I[u,v]$ of $u$ and $v$ is the the set of vertices that belong to some shortest $(u,v)$path. For any $S \subseteq V$, let $I[S]= \bigcup\_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is {\em geodesically convex} if $I[S] = S$. In other words, a subset $S$ is convex if, for any $u,v \in S$ and for any shortest $(u,v)$path $P$, $V(P) \subseteq S$. Given a subset $S\subseteq V$, the {\em convex hull} $I\_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a {\em hull set} of $G$ if $I\_h[S] = V$. The size of a minimum hull set of $G$ is the {\em hull number} of $G$, denoted by $hn(G)$. The {\sc Hull Number} problem is to decide whether $hn(G)\leq k$, for a given graph $G$ and an integer $k$. Dourado {\it et al.}
showed that this problem is NPcomplete in general graphs. In this paper, we answer an open question of Dourado et al.\~\cite{Douradoetal09} by showing that the {\sc Hull Number} problem is NPhard even when restricted to the class of bipartite graphs. Then, we design polynomial time algorithms to solve the {\sc Hull Number} problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in\~\cite{ACGSS11} to the class of $(q,q4)$graphs and to the class of cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an $n$node graph $G$ without simplicial vertices is at most $1+\lceil \frac{3(n1)}{5}\rceil$ in general, at most $1+\lceil \frac{n1}{2}\rceil$ if $G$ is regular or has no triangle, and at most $1+\lceil \frac{n1}{3}\rceil$ if $G$ has girth at least $6$. 
@techreport{ACG+11,
url = {http://hal.inria.fr/inria00576581/en/},
title = {{On the hull number of some graph classes}},
author = {J. Araujo and V. Campos and F. Giroire and N. Nisse and L. Sampaio and R. Soares},
abstract = {{In this paper, we study the geodetic convexity of graphs focusing on the problem of the complexity to compute inclusionminimum hull set of a graph in several graph classes. For any two vertices $u,v\in V$ of a connected graph $G=(V,E)$, the {\em closed interval} $I[u,v]$ of $u$ and $v$ is the the set of vertices that belong to some shortest $(u,v)$path. For any $S \subseteq V$, let $I[S]= \bigcup\_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is {\em geodesically convex} if $I[S] = S$. In other words, a subset $S$ is convex if, for any $u,v \in S$ and for any shortest $(u,v)$path $P$, $V(P) \subseteq S$. Given a subset $S\subseteq V$, the {\em convex hull} $I\_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a {\em hull set} of $G$ if $I\_h[S] = V$. The size of a minimum hull set of $G$ is the {\em hull number} of $G$, denoted by $hn(G)$. The {\sc Hull Number} problem is to decide whether $hn(G)\leq k$, for a given graph $G$ and an integer $k$. Dourado {\it et al.}
showed that this problem is NPcomplete in general graphs. In this paper, we answer an open question of Dourado et al.\~\cite{Douradoetal09} by showing that the {\sc Hull Number} problem is NPhard even when restricted to the class of bipartite graphs. Then, we design polynomial time algorithms to solve the {\sc Hull Number} problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in\~\cite{ACGSS11} to the class of $(q,q4)$graphs and to the class of cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an $n$node graph $G$ without simplicial vertices is at most $1+\lceil \frac{3(n1)}{5}\rceil$ in general, at most $1+\lceil \frac{n1}{2}\rceil$ if $G$ is regular or has no triangle, and at most $1+\lceil \frac{n1}{3}\rceil$ if $G$ has girth at least $6$.}},
pages = {19},
sorte = {Rapports},
institution = {INRIA},
number = {RR7567},
year = {2011},
month = Sep,
pdf = {http://hal.inria.fr/inria00576581/PDF/hnRR\_v2.pdf},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={no},
xpays = {BR},
}

F. Becker,
A. Kosowski,
N. Nisse,
I. Rapaport,
and K. Suchan.
Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power.
Technical report RR7746,
INRIA,
2011.
[WWW
] [PDF
]
Abstract: 
In this work we study the computational power of graphbased models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the current content of the whiteboard. When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology. We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not. This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty). We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the
second, and so on. Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one. These problems are related to Maximal Independent Set and detection of cycles. Finally we investigate problems related to connectivity as the construction of spanning or BFStree in our different models. 
@techreport{BKN+11,
url = {http://hal.inria.fr/inria00627910/en/},
title = {{Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power}},
author = {Becker, F. and Kosowski, A. and Nisse, N. and Rapaport, I. and Suchan, K.},
abstract = {{In this work we study the computational power of graphbased models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the current content of the whiteboard. When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology. We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not. This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty). We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the
second, and so on. Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one. These problems are related to Maximal Independent Set and detection of cycles. Finally we investigate problems related to connectivity as the construction of spanning or BFStree in our different models.}},
sorte = {Rapports},
institution = {INRIA},
number = {RR7746},
year = {2011},
pdf = {http://hal.inria.fr/inria00627910/PDF/RR7746.pdf},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={no},
xpays = {CL,PL},
}

S. Belhareth,
D. Coudert,
D. Mazauric,
N. Nisse,
and I. Tahiri.
Reconfiguration with physical constraints in WDM networks.
Research Report RR7850,
INRIA,
2011.
[WWW
] [PDF
]
Keywords:
Reconfiguration,
WDM,
NPcomplete,
Physical Layer Impaiments..
Abstract: 
In a WDM network, setting up a new wavelength in a fiber requires recalibrating the other wavelengths passing through this fiber. This induces a cost (e.g., time, energy, degradation of QoS) that depends nonlinearly on the number of wavelengths using the fiber. When a set of connection requests must change their optical paths in the network (e.g., during a maintenance operation on a link in the network), the order in which requests are switched affects the total cost of the operation. That is, the reconfiguration of the routing in a WDM network has some cost due to physical layer impairments. We initiate the study of the corresponding optimization problem by modeling the cost of switching a request as a nonlinear function depending on the load of the links used by the new lightpath. We prove that determining the optimal rerouting order is NPcomplete for a $2$nodes network. We then give general lower and upper bounds on the minimum cost and we identify classes of instances where the problem
can be solved in polynomial time. Finally, we design heuristics for this problem and we analyze and compare them by simulations. 
@techreport{BCM+11c,
AUTHOR = {Belhareth, S. and Coudert, D. and Mazauric, D. and Nisse, N. and Tahiri, I.},
TITLE = {{Reconfiguration with physical constraints in WDM networks}},
TYPE = {Research Report},
YEAR = {2011},
KEYWORDS = {Reconfiguration, WDM, NPcomplete, Physical Layer Impaiments.},
INSTITUTION = {INRIA},
NUMBER = {RR7850},
URL = {http://hal.inria.fr/hal00654111/en},
PDF = {http://hal.inria.fr/docs/00/65/41/11/PDF/RR7850.pdf},
abstract = {In a WDM network, setting up a new wavelength in a fiber requires recalibrating the other wavelengths passing through this fiber. This induces a cost (e.g., time, energy, degradation of QoS) that depends nonlinearly on the number of wavelengths using the fiber. When a set of connection requests must change their optical paths in the network (e.g., during a maintenance operation on a link in the network), the order in which requests are switched affects the total cost of the operation. That is, the reconfiguration of the routing in a WDM network has some cost due to physical layer impairments. We initiate the study of the corresponding optimization problem by modeling the cost of switching a request as a nonlinear function depending on the load of the links used by the new lightpath. We prove that determining the optimal rerouting order is NPcomplete for a $2$nodes network. We then give general lower and upper bounds on the minimum cost and we identify classes of instances where the problem
can be solved in polynomial time. Finally, we design heuristics for this problem and we analyze and compare them by simulations.},
}

JC. Bermond,
A. JeanMarie,
D. Mazauric,
and J. Yu.
Well Balanced Designs for Data Placement.
Research Report 7725,
INRIA,
09 2011.
[WWW
]
Abstract: 
The problem we consider in this article is motivated by
data placement in particular data replication in video on demand
systems. We are given a set $V$ of $n$ servers and $b$ files (data,
documents). Each file is replicated on exactly $k$ servers. A
placement consists in finding a family of $b$ subsets of $V$
(representing the files) called blocks each of size $k$. Each server
has some probability to fail and we want to find a placement which
minimizes the variance of the number of available files. It was
conjectured that there always exists an optimal placement (with
variance better than that of any other placement for any value of the
probability of failure). We show that the conjecture is true, if there
exists a well balanced design, that is a family of blocks, such that
each jelement subset of $V$ , $1 \leq j \leq k$, belongs to the same
or almost the same number of blocks (difference at most one). The
existence of well balanced designs is a difficult problem as it
contains as subproblem the existence of Steiner systems. We completely
solve the case $k=2$ and give bounds and constructions for $k = 3$ and
some values of $n$ and $b$. 
@techreport{BJMY11,
author = {Bermond, JC. and JeanMarie, A. and Mazauric, D. and Yu, J.},
title = {Well Balanced Designs for Data Placement},
year = {2011},
month = {09},
institution = {INRIA},
number = {7725},
type = {Research Report},
url= {http://hal.inria.fr/inria00618656},
abstract = {The problem we consider in this article is motivated by
data placement in particular data replication in video on demand
systems. We are given a set $V$ of $n$ servers and $b$ files (data,
documents). Each file is replicated on exactly $k$ servers. A
placement consists in finding a family of $b$ subsets of $V$
(representing the files) called blocks each of size $k$. Each server
has some probability to fail and we want to find a placement which
minimizes the variance of the number of available files. It was
conjectured that there always exists an optimal placement (with
variance better than that of any other placement for any value of the
probability of failure). We show that the conjecture is true, if there
exists a well balanced design, that is a family of blocks, such that
each jelement subset of $V$ , $1 \leq j \leq k$, belongs to the same
or almost the same number of blocks (difference at most one). The
existence of well balanced designs is a difficult problem as it
contains as subproblem the existence of Steiner systems. We completely
solve the case $k=2$ and give bounds and constructions for $k = 3$ and
some values of $n$ and $b$.},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
xpays = {MA},
sorte = "Rapports",
}

S. Bessy and F. Havet.
Enumerating the edgecolourings and total colourings of a regular graph.
Research Report RR7652,
INRIA,
June 2011.
[WWW
] [PDF
]
Abstract: 
In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$edgecolourings of a $k$regular graph on $n$ vertices is $k\cdot(k1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$edgecolourings of a $k$regular graph using a time $O^*((k1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.\~\cite{GKC10}. We also show that the number of $4$totalcolourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$totalcolourings of a connected cubic graph. 
@techreport{BeHa11,
hal_id = {inria00602188},
url = {http://hal.inria.fr/inria00602188/en/},
title = {{Enumerating the edgecolourings and total colourings of a regular graph}},
author = {S. Bessy and F. Havet},
abstract = {{In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$edgecolourings of a $k$regular graph on $n$ vertices is $k\cdot(k1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$edgecolourings of a $k$regular graph using a time $O^*((k1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.\~\cite{GKC10}. We also show that the number of $4$totalcolourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$totalcolourings of a connected cubic graph.}},
language = {Anglais},
type = {Research Report},
affiliation = {Laboratoire d'Informatique de Robotique et de Micro\'electronique de Montpellier  LIRMM  CNRS : UMR5506  Universit\'e Montpellier II  Sciences et Techniques du Languedoc  MASCOTTE  INRIA Sophia Antipolis / Laboratoire I3S  INRIA  Universit\'e de Nice SophiaAntipolis  CNRS : UMR6070},
institution = {INRIA},
number = {RR7652},
year = {2011},
month = Jun,
pdf = {http://hal.inria.fr/inria00602188/PDF/RR7652.pdf},
xeditorialboard={no},
xproceedings={yes},
xinternationalaudience={yes},
}

V. Campos and F. Havet.
5choosability of graphs with 2 crossings.
Research Report RR7618,
INRIA,
05 2011.
[WWW
] [PDF
]
Abstract: 
{W}e show that every graph with two crossings is 5choosable. {W}e also prove that every graph which can be made planar by removing one edge is 5choosable. 
@techreport{CaHa11,
URL = {http://hal.inria.fr/inria00593426/en/},
title = { 5choosability of graphs with 2 crossings},
author = {V. Campos and F. Havet},
abstract = {{W}e show that every graph with two crossings is 5choosable. {W}e also prove that every graph which can be made planar by removing one edge is 5choosable.},
language = {{A}nglais},
affiliation = {{L}aborat{\'o}rios de {P}esqu{I}sa em {C}omput{A}{\c{c}}{\~a}o  {LIA}  {U}niversite {F}ederale du {C}eara  {MASCOTTE}  {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S}  {INRIA}  {U}niversit{\'e} de {N}ice {S}ophia{A}ntipolis  {CNRS} : {UMR}6070},
pages = {22},
type = {Research Report},
institution = {INRIA},
number = {{RR}7618},
month = {05},
year = {2011},
PDF = {http://hal.inria.fr/inria00593426/PDF/RR7618.pdf},
xpays={BR},
}

J. G. Chang,
F. Havet,
M. Montassier,
and A. Raspaud.
Steinberg's Conjecture and nearcolorings.
Rapport de recherche RR7669,
INRIA,
7 2011.
[WWW
] [PDF
]
Abstract: 
Let ${\cal F}$ be the family of planar graphs without cycles of length
4 and 5. Steinberg's Conjecture (1976) that says every graph of ${\cal
F}$ is 3colorable remains widely open. Motiv\'ees par une relaxation propos\'ee par Erd\H{o}s (1991), plusieurs
\'etudes ont montr\'e la conjecture pour des sousclasses de ${\cal F}$. Par exemple, Borodin {\it et al.}~ont prouv\'e
que tout graphe planaire sans cycles de longueur 4 \`a 7 est
3colorable. Dans ce rapport, nous relaxons le probl\`eme non pas sur la classe de graphes mais
sur le type de coloration en consid\'erant des {\em quasicolorations}.
Un graphe $G=(V,E)$ est dit $(i,j,k)$colorable
si son ensemble de sommet peut \^etre partitionner en trois ensembles $V_1,V_2,V_3$
tels que les graphes $G[V_1],G[V_2],G[V_3]$ induits par ces ensembles soit de degr\'e maximum au plus $i,j,k$
respectivement. Avec cette terminologie, la Conjecture de Steinberg dit que
tout graphe de ${\cal F}$ est $(0,0,0)$colorable. Un r\'esultat de Xu (2008)
implique que tout graphe de ${\cal F}$ est $(1,1,1)$colorable. Nous montrons ici que tout graphe de ${\cal F}$ est $(2,1,0)$colorable et
$(4,0,0)$colorable. 
@techreport{CHM+11,
url = {http://hal.inria.fr/inria00605810/en/},
title = {{Steinberg's Conjecture and nearcolorings}},
author = {J. G. Chang and F. Havet and M. Montassier and A. Raspaud},
abstract = {Let ${\cal F}$ be the family of planar graphs without cycles of length
4 and 5. Steinberg's Conjecture (1976) that says every graph of ${\cal
F}$ is 3colorable remains widely open. Motiv\'ees par une relaxation propos\'ee par Erd\H{o}s (1991), plusieurs
\'etudes ont montr\'e la conjecture pour des sousclasses de ${\cal F}$. Par exemple, Borodin {\it et al.}~ont prouv\'e
que tout graphe planaire sans cycles de longueur 4 \`a 7 est
3colorable. Dans ce rapport, nous relaxons le probl\`eme non pas sur la classe de graphes mais
sur le type de coloration en consid\'erant des {\em quasicolorations}.
Un graphe $G=(V,E)$ est dit $(i,j,k)$colorable
si son ensemble de sommet peut \^etre partitionner en trois ensembles $V_1,V_2,V_3$
tels que les graphes $G[V_1],G[V_2],G[V_3]$ induits par ces ensembles soit de degr\'e maximum au plus $i,j,k$
respectivement. Avec cette terminologie, la Conjecture de Steinberg dit que
tout graphe de ${\cal F}$ est $(0,0,0)$colorable. Un r\'esultat de Xu (2008)
implique que tout graphe de ${\cal F}$ est $(1,1,1)$colorable. Nous montrons ici que tout graphe de ${\cal F}$ est $(2,1,0)$colorable et
$(4,0,0)$colorable.},
language = {Anglais},
affiliation = {Department of Mathematics  National Taiwan University  Taida Insitute for Mathematical Science  National Taiwan University  National Taiwan University  National Center for Theoretical Science  National Center for Theoretical Science  MASCOTTE  INRIA Sophia Antipolis / Laboratoire I3S  INRIA  Universit{\'e} de Nice SophiaAntipolis  CNRS : UMR6070  Laboratoire Bordelais de Recherche en Informatique  LaBRI  CNRS : UMR5800  Universit{\'e} Sciences et Technologies  Bordeaux I  Ecole Nationale Sup{\'e}rieure d'Electronique, Informatique et Radiocommunications de Bordeaux  Universit{\'e} Victor Segalen  Bordeaux II},
type = {Rapport de recherche},
institution = {INRIA},
number = {RR7669},
collaboration = {NSC Taiwan, NSC992923M002007MY3 },
year = {2011},
month = {7},
pdf = {http://hal.inria.fr/inria00605810/PDF/RR7669.pdf},
xpays={CN},
xeditorialboard={yes},
xproceedings={yes},
xinternationalaudience={yes},
}

F. Fomin,
F. Giroire,
A. JeanMarie,
D. Mazauric,
and N. Nisse.
To Satisfy Impatient Web surfers is Hard.
Technical report RR7740,
INRIA,
September 2011.
[WWW
] [PDF
]
Abstract: 
Prefetching is a basic mechanism to avoid to waste time when accessing data. However, a tradeoff must be established between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while an Internaut is surfing on the Web. Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching and that ensures that all documents accessed by the web surfer have previously been loaded in the cache. We model this problem as a game similar to Cops and Robber Games in graphs. A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she
enters an unmarked vertex. The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does. We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex. All our results hold for both variants, connected or not. We show that deciding whether the surveillance number of a chordal graph equals 2 is NPhard. Deciding if the surveillance number of a DAG equals 4 is PSPACEcomplete. Moreover, computing the surveillance number is NPhard in split graphs. On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number. 
@techreport{FGJ+11,
url = {http://hal.inria.fr/inria00625703/en/},
title = {{To Satisfy Impatient Web surfers is Hard}},
author = {Fomin, F. and Giroire, F. and JeanMarie, A. and Mazauric, D. and Nisse, N.},
abstract = {{Prefetching is a basic mechanism to avoid to waste time when accessing data. However, a tradeoff must be established between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while an Internaut is surfing on the Web. Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching and that ensures that all documents accessed by the web surfer have previously been loaded in the cache. We model this problem as a game similar to Cops and Robber Games in graphs. A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she
enters an unmarked vertex. The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does. We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex. All our results hold for both variants, connected or not. We show that deciding whether the surveillance number of a chordal graph equals 2 is NPhard. Deciding if the surveillance number of a DAG equals 4 is PSPACEcomplete. Moreover, computing the surveillance number is NPhard in split graphs. On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.}},
pages = {20},
sorte = {Rapports},
institution = {INRIA},
number = {RR7740},
year = {2011},
month = Sep,
pdf = {http://hal.inria.fr/inria00625703/PDF/RR7740.pdf},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={no},
xpays = {NO},
}

F. Giroire,
S. K. Gupta,
R. Modrzejewski,
J. Monteiro,
and S. Pérennes.
Analysis of the Repair Time in Distributed Storage Systems.
Research Report RR7538,
INRIA,
02 2011.
[WWW
] [PDF
]
Keywords:
P2P storage systems,
data lifetime,
queuing model,
regenerating codes per formance evaluation.
Abstract: 
{D}istributed or peertopeer storage systems introduce redundancy to preserve the data in case of peer failures or departures. {T}o ensure longterm fault tolerance, the storage system must have a selfrepair service that continuously reconstructs lost fragments of redundancy. {T}he speed of this reconstruction process is crucial for the data survival. {T}his speed is mainly determined by available bandwidth, a critical resource of such systems. {W}e propose a new analytical framework that takes into account the correlation of concurrent repairs when estimating the repair time and the probability of data loss. {M}ainly, we intro duce queuing models in which reconstructions are served by peers at a rate that depends on the available bandwidth. {T}he models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the {G}rid'5000 testbed platform. 
@techreport{GGM+11,
url = {http://hal.inria.fr/inria00565359/en/},
title = { {A}nalysis of the {R}epair {T}ime in {D}istributed {S}torage {S}ystems},
author = {Giroire, F. and Gupta, S. K. and Modrzejewski, R. and Monteiro, J. and P{\'e}rennes, S.},
abstract = {{D}istributed or peertopeer storage systems introduce redundancy to preserve the data in case of peer failures or departures. {T}o ensure longterm fault tolerance, the storage system must have a selfrepair service that continuously reconstructs lost fragments of redundancy. {T}he speed of this reconstruction process is crucial for the data survival. {T}his speed is mainly determined by available bandwidth, a critical resource of such systems. {W}e propose a new analytical framework that takes into account the correlation of concurrent repairs when estimating the repair time and the probability of data loss. {M}ainly, we intro duce queuing models in which reconstructions are served by peers at a rate that depends on the available bandwidth. {T}he models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the {G}rid'5000 testbed platform.},
keywords = {{P}2{P} storage systems, data lifetime, queuing model, regenerating codes per formance evaluation},
language = {{A}nglais},
affiliation = {{MASCOTTE}  {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S}  {INRIA}  {U}niversit{\'e} de {N}ice {S}ophia{A}ntipolis  {CNRS} : {UMR}6070  {I}ndian {I}nstitute of {T}echnology [{D}elhi]  {IIT} {D}elhi  {I}ndian {I}nstitute of {T}echnology {D}elhi },
pages = {28},
type = {Research Report},
institution = {INRIA},
number = {{RR}7538},
month = {02},
year = {2011},
pdf = {http://hal.inria.fr/inria00565359/PDF/RR7538.pdf},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
xpays = {BR},
}

F. Havet and X. Zhu.
The game Grundy number of graphs.
Rapport de recherche RR7646,
INRIA,
June 2011.
[WWW
] [PDF
]
Keywords:
colouring game,
game Grundy number,
trees,
partial 2trees.
Abstract: 
Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2tree is at most 7. 
@techreport{HaZh11,
url = {http://hal.inria.fr/inria00600738/en/},
title = {{The game Grundy number of graphs}},
author = {F. Havet and X. Zhu},
abstract = {{Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2tree is at most 7.}},
keywords = {colouring game, game Grundy number, trees, partial 2trees},
language = {Anglais},
affiliation = {MASCOTTE  INRIA Sophia Antipolis / Laboratoire I3S  INRIA  Universit\'e de Nice SophiaAntipolis  CNRS : UMR6070  Department of Mathematics  Zhejiang Normal University},
type = {Rapport de recherche},
institution = {INRIA},
number = {RR7646},
year = {2011},
month = Jun,
pdf = {http://hal.inria.fr/inria00600738/PDF/RR7646.pdf},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
xpays={CN},
}

F. Maffray and G. Morel.
On 3colorable $P_5$free graphs.
Technical report 191,
Les Cahiers Leibniz, Laboratoire GSCOP,
2011.
[PDF
]
@techreport{MaMo11a,
title = {{On 3colorable $P_5$free graphs}},
author={Maffray, F. and Morel, G.},
number = {191},
institution={Les Cahiers Leibniz, Laboratoire GSCOP},
year={2011},
pdf={https://consultcahiersleibniz.gscop.grenobleinp.fr/WebObjects/ProjetCahiersLeibniz.woa/Contents/WebServerResources/CahiersLeibniz/cahiers/Cahier191.pdf},
xeditorialboard = {no},
xproceedings = {no},
xinternationalaudience = {yes},
sorte = "Rapports"
}

J. Moulierac,
T. K. Phan,
N. Thoai,
and C. Tran.
Xcast6 Treemap Islands  A Mixed Model of Application and Network Layer Multicast.
Rapport de recherche RR7784,
INRIA,
December 2011.
[WWW
] [PDF
]
Keywords:
IP multicast,
Application Layer Multicast,
Xcast,
media streaming,
linear program,
algorithms.
Abstract: 
IP multicast is a protocol that deals with group communications with the aim of reducing traffic redundancy in the network. However, due to difficulty in deployment and poor scalability with a large number of multicast groups, IP multicast is still not widely deployed and used on the Internet. Recently, Xcast6 and Xcast6 Treemap, the two network layer multicast protocols, have been proposed with complementary scaling properties to IP multicast: they support a very large number of active multicast sessions. However, the key limitation of these protocols is that they only support small multicast group. In this paper, we propose Xcast6 Treemap island  a hybrid model of Application Layer Multicast (ALM) and Xcast6 that can work for large multicast group. Our model has several key advantages: ease of deployment, efficiency in bandwidth savings, no control message between endhost and router, zero multicast forwarding state at router and no need for a multicast address allocation protocol. In
addition, this model is a potential service from which an ISP can get new revenue. Finally, in simulation section, we have made a comparison with IP multicast and NICE protocol to show the feasibility of our new model. 
@techreport{Mou11,
hal_id = {inria00637656},
url = {http://hal.inria.fr/inria00637656/en/},
title = {{Xcast6 Treemap Islands  A Mixed Model of Application and Network Layer Multicast}},
author = {J. Moulierac and T. K. Phan and N. Thoai and C. Tran},
abstract = {{IP multicast is a protocol that deals with group communications with the aim of reducing traffic redundancy in the network. However, due to difficulty in deployment and poor scalability with a large number of multicast groups, IP multicast is still not widely deployed and used on the Internet. Recently, Xcast6 and Xcast6 Treemap, the two network layer multicast protocols, have been proposed with complementary scaling properties to IP multicast: they support a very large number of active multicast sessions. However, the key limitation of these protocols is that they only support small multicast group. In this paper, we propose Xcast6 Treemap island  a hybrid model of Application Layer Multicast (ALM) and Xcast6 that can work for large multicast group. Our model has several key advantages: ease of deployment, efficiency in bandwidth savings, no control message between endhost and router, zero multicast forwarding state at router and no need for a multicast address allocation protocol. In
addition, this model is a potential service from which an ISP can get new revenue. Finally, in simulation section, we have made a comparison with IP multicast and NICE protocol to show the feasibility of our new model.}},
keywords = {IP multicast, Application Layer Multicast, Xcast, media streaming, linear program, algorithms},
language = {Anglais},
affiliation = {MASCOTTE  INRIA Sophia Antipolis / Laboratoire I3S  INRIA  Universit{\'e} de Nice SophiaAntipolis  CNRS : UMR6070  Faculty of Mechanical Engineering [HCM University]  FME  Ho CHi Minh City University of Technology},
pages = {27},
type = {Rapport de recherche},
institution = {INRIA},
number = {RR7784},
year = {2011},
month = Dec,
xpays = {VN},
xeditorialboard={no},
xproceedings={no},
xinternationalaudience={yes},
sorte = "Rapports",
pdf = {http://hal.inria.fr/inria00637656/PDF/RR7784.pdf},
}