Second Meeting

Date: June 22-24, 2009
Location : room F111, Université Joseph Fourier, Grenoble, France

Schedule of the meeting


  • 10h-12h: A. Parreau - "dynamic radius codes in the cycle"
  • 12h30: lunch
  • 14h-17h: L. Beaudou - PhD defense


  • 9h-10h30: F. Foucaud - "identifying codes and the maximum degree"
  • 10h30-12h: discussion
  • 12h30: lunch
  • 14h-15h30: A. Pêcher - "linear programming for identifying codes"
  • 15h30 - 18h: discussion
  • 20h: dinner


  • 10h-11h: open discussion
  • 11h-12h30: E. Sopena - "identifying codes in evolving graphs"
  • 13h: lunch
  • 14h-16h: open discussion

Minutes of the meeting

Participants: L. Beaudou, P. Dorbec, F. Foucaud, S. Gravier, R. Klasing, A. Parreau, A. Pêcher, A. Raspaud, E. Sopena


  • 10h-12h: A. Parreau: dynamic radius codes in the cycle definitions of two generalizations of r-identifying codes (IC) with dynamic radius - weak r-identifying codes (WIC) and half-weak r-identifying codes (HWIC). WICs generalize ICs and HWICs generalize WICs. Weak 1-identifying codes are equivalent to locating-dominating sets. Optimal cardinalities of WICs and HWICs in the cycle Cn are given.


  • 9h-10h30: F. Foucaud: identifying codes and the maximum degree known lower bound for the minimum cardinality of a 1-identifying code in graphs of maximum degree Delta - characterization and construction of all graphs reaching this bound - general upper bound for the minimum cardinality of a 1-identifying code - several upper bounds for this value with respect to the maximum degree in the general case, in regular graphs, in triangle-free graphs, in graphs of girth at least 5, and in subcubic graphs
  • 10h30-12h: discussion 1-identifying codes in Sierpinski graphs - 1-identifying codes in products of graphs: products of paths, products of cycles (tori), products of a path and a clique
  • 14h-15h30: A. Pêcher: linear programming for identifying codes presentation of constraints for linear programmes used for computing optimal ICs, WICs and HWICs - using continuous variables to characterize IC polytopes - relationship with weighted ICs - usefulness for lower bounds on discrete ICs
  • 15h30-18h: discussion 1-identifying codes in some circulant graphs


  • 10h-11h: discussion locating sets (Slater, 1975) allow identification of vertices using distances - relationship between locating sets and Half Weak r-identifying codes: a locating set is a Half Weak diam(G)-identifying code - locating sets in trees, cycles, chains - graphs for which an optimal locating set has cardinality 1 or 2 - locating colorings (Slater et. al, 2002) - relationship between locating sets, the locating chromatic number and the chromatic number: is it easy to construct a locating-coloring using a locating set?
  • 11h-12h30: E. Sopena: identifying codes in evolving graphs identifying codes in increasing paths - use of local rewriting rules to construct dynamic identifying codes - use of distributed local algorithms - termination and convergence time of the algorithm, optimality ratios
  • 14h-16h: discussion organizational questions: report, next meeting in autumn

The project?



edit SideBar