Third Meeting

Date: November 17-18, 2009
Location : room 178, LaBRI, Bordeaux, France

Schedule of the meeting


  • 10h: Welcome
  • 10h30-11h30: M. Kovse - "Self similar Graphs and Identifying problems"
  • 11h30-12h30: Discussion
  • 12h30: lunch
  • 14h-15h: E. Guerrini - "Identifying vertex coloring"
  • 15h-18h: Discussion
  • 20h: dinner


  • 10h-11h: F. Foucaud - "Identification with paths"
  • 11h-12h: Discussion
  • 12h30: lunch
  • 14h-15h: A. Parreau - "Generalization of weak and light identifying codes"
  • 15h-16h: F. Foucaud - "Online domination, location and identification in trees"

Minutes of the meeting

Participants: O. Delmas, P. Dorbec, F. Foucaud, S. Gravier, E. Guerrini, R. Klasing, M. Kovse, M. Montassier, R. Naserasr, A. Parreau, A. Pêcher (via visioconf.), A. Raspaud, E. Sopena, P. Valicov, G. Zemor.


  • 10h30-11h30: M. Kovse: Self similar Graphs and Identifying problems

Recall definition of Sierpinski graphs and link with towers of Hanoï - Identifying codes on Sierpinski graphs - definition of self similar graphs (generalization of Sierpinski graphs) - proposition of similar problems than for Sierpinski for self similar graphs : formal definition (link with wreath product?), adjacency, incidence matrix, identifying codes, chromatic number - Sierpinski gasket graphs - Regularizing Sierpinski graphs - some geometrical representations of the hypercube.

  • 14h-15h: E. Guerrini: Identifying vertex coloring

Definition of identifying chromatic number : min number of colors of a (not necessarily proper) coloring of the vertices such that the set of colors in the neighbourhood of a vertex identifies it - characterize maximum graphs of a class identifyable with a fixed number of colors - identifying chromatic number bounded by size of an identifying code +1 - technique for finding an identifying proper coloring of a path (of good length) that provides almost every triples of colors (describing walks on a complete graph).


  • 10h-11h: F. Foucaud: Identification with paths

Recall definitions of locating domination, Identifying codes, open neighbourhood locating dominating, locating set/metric base, identification with cycles, with paths - for identifiction with paths, exact value for cliques, hypercubes (log n), cycles and paths, bounds for trees.

  • 11h30-12h: Problems to be done
* Characterize circulant graphs st given p and r,\forall u,v, d(u,v)=p, symmetric difference of balls of radius r centered on u and v is of size 2. [Sylvain: André, Paul]
* Polyhedral aspects of identifying-codes [Sylvain: Arnaud, Petru]
* Local version of identifying coloring presented by E.Guerrini [Mickael: Eleonora, Matjaz]
* Online algorithms [Florent: Petru]
* Adaptative identification with patterns [Sylvain : Eleonora]
  • 14h-15h: A.Parreau: Generalization of weak and light identifying codes

Recall definitions of weak and light identifying codes - generalized definition of Parreau-Identifying codes - results on paths/cycles.

  • 15h-16h: F.Foucaud: Online Dominating set, locating dominating set, Identifying codes

Definition of an online algorithm - definition of its performance ratio - recall Eidenbenz results for domination in trees when you may just add vertex at distance 1 - show new algorithm for domination in trees at distance 1 (just add) - locating domination and identifying codes ratios for trees.

The project?



edit SideBar