References of "Gravier, Sylvain"
     in
Bookmark and Share    
Full Text
See detailLinear formulation of identifying cdes in graphs
Vandomme, Elise ULg; Gravier, Sylvain; Parreau, Aline ULg

Poster (2013, September 09)

Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The ... [more ▼]

Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The placement of sensors in the rooms corresponds to choosing a subset of vertices. Finding a sensor-placement such that the location of a fire in one room can be precisely determined is equivalent to constructing an identifying code in the graph. These are dominating sets of vertices for which the closed neighbourhood of each vertex (i.e., the vertex and its neighbours) has a unique intersection with the set. The problem of finding an identifying code has been widely studied. Yet its formulation as an integer linear problem hasn't been much considered. Let G be a graph with vertex set V, to an identifying code $C\subseteq V$ of $G$ correspond weights x_u (x_u is 1 if u belongs to C, otherwise x_u is 0) satisfying the following : for all vertices u,v * the sum of the x_w for w in the closed neighbourhood of u is at least 1 * the sum of the x_w for w in the symmetric difference of the closed neighbourhoods of u and v is at least 1. Of course, it is interesting to find an identifying code with the smallest possible cardinality. But in general this is a NP-hard problem. A way to obtain bounds on the minimal cardinality is to consider the associated linear problem where the weights x_u are fractional. In the case of vertex-transitive graphs, the minimal cardinality for the fractional case can only take two values which depend on the number of vertices, the degree of the graph and the smallest symmetric difference between any two closed neighbourhoods. We show that for an infinite family of graphs the bound is tight and for another another the bound is far too be reached. [less ▲]

Detailed reference viewed: 13 (5 ULg)
Full Text
Peer Reviewed
See detailConstant 2-labelling of weighted cycles
Gravier, Sylvain; Vandomme, Elise ULg

Conference (2012, November)

We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2 ... [more ▼]

We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2-coloring (black and white) of its vertex set which preserves the sum of the weight of black vertices under some automorphisms. In this manuscript, we study this problem on weighted complete graphs and on weighted cycles. Our results on cycles allow us to determine (r,a,b)-codes in Z^2 whenever |a-b|>4 and r>1. [less ▲]

Detailed reference viewed: 10 (1 ULg)
Full Text
Peer Reviewed
See detailConstant 2-labelling of a graph
Gravier, Sylvain; Vandomme, Elise ULg

Conference (2012, September)

We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2 ... [more ▼]

We introduce the concept of constant 2-labelling of a weighted graph and show how it can be used to obtain periodic sphere packing. Roughly speaking, a constant 2-labelling of a weighted graph is a 2-coloring (black and white) of its vertex set which preserves the sum of the weight of black vertices under some automorphisms. In this manuscript, we study this problem on weighted complete graphs and on weighted cycles. Our results on cycles allow us to determine (r,a,b)-codes in Z^2 whenever |a-b|>4 and r>1. [less ▲]

Detailed reference viewed: 3 (1 ULg)
Full Text
See detailColoring of the infinite grid
Vandomme, Elise ULg; Gravier, Sylvain

Poster (2012, May 23)

We present a method that links (r,a,b)-codes in the infinite grid and particular colorings of weighted cycles, called constant 2-labellings.

Detailed reference viewed: 23 (7 ULg)