**Sixth Meeting**

Date: April 04-08, 2011

Location : room 178, LaBRI, Bordeaux, France

## Schedule of the meeting

### Monday

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

### Tuesday

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

### Wednesday

- 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

### Thursday

- 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

### Friday

- 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.

*Monday*

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

*Tuesday*

*Open discussions, research problems proposals continued*

*Wednesday*

- 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

*Thursday*

- 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

*Friday*

- 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)*