Journée de l'équipe GAMoC – Jeudi 10 juillet 2014 à Orléans

La journée se tiendra en Espace Communication du LIFO.

Programme

10h00‒10h30Accueil
10h30‒11h30Ioan Todinca
11h30‒12h30Discussion fédération avec Mirian Halfeld Ferrari
12h30‒14h00Déjeuner à L'Agora
14h00‒14h30Retour sur le rapport avec Christophe Paul (en visio.)
14h30‒15h00Réunion d'équipe
15h00‒16h00Florent Becker
16h00‒17h00Romain Letourneur


Les créneaux restant relativement souples.

Exposés scientifiques

Florent Becker, La loi de la nanojungle : la coopération n'est pas (strictement) meilleure que la compétition dans l'auto-assemblage


Romain Letourneur, On the number of minimal dominating sets on cobipartite, split and interval graphs
Joint work with J.-F. Couturier and M. Liedloff.

Abstract. A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159n) minimal dominating sets. Here we establish upper bounds on this maximum number of minimal dominating sets for cobipartite and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For interval graphs, we show that the number of minimal dominating sets is at most 3n/3~1.4423n, which is the best possible bound. For cobipartite graphs, we lower the O(1.5875n) upper bound from Couturier to O(1.4511n).


Ioan Todinca, The simultaneous number-in-hand communication model for networks: private coins, public coins and determinism
Joint work with Florent Becker, Pedro Montealegre and Ivan Rapaport (Univ. Chile).

Abstract. We study the multiparty communication model where players are the nodes of a network and each of these players knows his/her own identifier together with the identifiers of his/her neighbors. The players simultaneously send a unique message to a referee who must decide a graph property. The goal of this article is to separate, from the point of view of message size complexity, three different settings: deterministic protocols, randomized protocols with private coins and randomized protocols with public coins. For this purpose we introduce the boolean function Twins. This boolean function returns 1 if and only if there are two nodes with the same neighborhood.


Retour aux évènements 2014