References of "Gravier, Sylvain"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailIdentifying codes in vertex-transitive graphs
Gravier, Sylvain; Parreau, Aline ULg; Rottey, Sara et al

Conference (2014, July)

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) where V is the ... [more ▼]

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the optimal integer and fractional solutions is between 1 and 2 log(|V|) where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order |V|^a with a in {1/4, 1/3, 2/5}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs. [less ▲]

Detailed reference viewed: 18 (4 ULg)
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: 28 (15 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: 17 (4 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: 7 (2 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: 30 (10 ULg)