Evènement pour le groupe Algorithmique Distribuée

Date 2018-01-22  14:00-15:00
TitreOn the simplification of temporal cliques 
RésuméIn the context of this talk, a temporal clique is a complete graph with a unique integer label on every edge. This number can be thought of as the only date at which both endpoints interact. In a recent article, Akrida, Gasieniek, Mertzios, and Spirakis show that n/4 well chosen edges can be removed in such a graph without breaking temporal connectivity (i.e. maintaining increasing paths (journeys) between every pair of nodes, in both directions). In this talk, I will present a three-steps proof which gradually improves upon this result. The first step shows that (n^2)/8 edges (i.e. one quarter of the edges) can be removed; the second step, building upon the first, shows that half of the edges can actually be removed; then the third step, building upon the other two, shows that all edges but O(n) can actually be removed. This is obviously tight (up to a constant factor). Characterizing the exact factor that our proof yields is still work in progress. On the other hand, we give a conjecture as to the exact number of edges which can be removed (à un près), supported by extensive simulations. 
OrateurArnaud Casteigts 

Aucun document lié à cet événement.

Retour à l'index