Sixth Meeting

Date: April 04-08, 2011
Location : room 178, LaBRI, Bordeaux, France

Schedule of the meeting


  • 10h-12h: open discussion / proposal of research problems
  • 12h30: lunch
  • 14h-15h: open discussion / open problems in distributed algorithms
  • 15h-18h: open discussion


  • 10h-12h: open discussion
  • 12h30: lunch
  • 14h-18h: open discussion


  • 9h30-11h: Reza Naserasr - "Identifying Codes in Line Graphs"
  • 11h-12h: Open Problem Session
  • 12h30: lunch
  • 14h-15h: Petru Valicov - "Complexity on different types of identification"
  • 15h-18h: open discussion


  • 9h30-11h: Tero Laihonen - "The optimal density of 2-identifying codes in the hexagonal mesh" (chair; Julien Moncel)
  • 11h-12h: open discussion
  • 12h30: lunch
  • 14h-15h: Florent Foucaud - "Bounding the identifying code number of a graph using its degree parameters, a probabilistic approach"
  • 15h-18h: open discussion
  • 19h30: dinner


  • 9h30-10h30: discussion (state of the art IDEA + workshop)
  • 10h30-12h: Aline Parreau - "Identifying codes using robust euclidean balls"
  • 12h15: lunch
  • 14h-15h: Martin Skoviera - "Nowhere-zero flows on signed eulerian graphs"
  • 15h-16h: open discussion

Minutes of the meeting

Participants: L. Beaudou, O. Delmas, P. Dorbec, F. Foucaud, R. Klasing, T. Laihonen, J. Moncel, M. Montassier, R. Naserasr, A. Parreau, A. PÍcher, A. Raspaud, G. Renault, E. Rollova, E. Sopena, P. Valicov, A. Wagler.


Open discussions, research problems proposals Adaptive identifying codes, LID-chromatic number, ID codes in interval graphs, circulant graphs, cartesian products of graphs


Open discussions, research problems proposals continued


  • 10h-12h: Reza Naserasr - Line-identifying codes

Definition of the concept, lower and upper bounds, bounds for a given average degree, open problems

  • 14h-16h: Petru Valicov - Complexity on different types of identification

NP-hardness of 1-IDCODE in split graphs, line graphs. NP-hardness of 4-LID-COLORING in planar graphs. Open problems. SLIDES


  • 10h-12h: Tero Laihonen - The optimal density of 2-identifying codes in the hexagonal mesh

Lower and upper bounds for infinite hexagonal grids, paths and cycles. Discharging techniques. SLIDES

  • 14h-16h: Florent Foucaud - Bounding the identifying code number of a graph using its degree parameters, a probabilistic approach

Upper bound using The Local Lemma. Expected value of the identifying code number in a random regular graph. SLIDES


  • 10h-11h: Discussions about the IDEA project
  • 11h-12h: Aline Parreau - Identifying codes using robust euclidean balls

Robust identification in the grid plane with various radii, lower and upper bounds SLIDES

  • 14h-16h: Martin Skoviera - Nowhere-zero flows on signed eulerian graphs (weekly seminar of the G&A team)

The project?



edit SideBar