Résumé | Résumé : As a new post-doc student in ANR IDEA, I would be glad to present two problems I've been studying during my stay in Montreal this winter.
Broadcast in networks: the problem consists in finding an optimal protocol to collect in one specific node, information of the whole networks. The constraint is that each node cannot send more than one unit of information at a time. We provide a polynomial algorithm and discuss about some esthetics.
Absorbing sets in arc-coloured tournament: this problem, attributed to Erdös, deals with absorbing sets in arc-coloured tournaments. A set S of vertices is said absorbing if any vertex out of S admits a monochromatic chain to some vertex of S. Can the size of a minimum absorbing set be bounded above by a function of the number of colours? We will present some known result and state open questions. |