Newer
Older
# Sujet n° 13 : Connexité dans des graphes temporels
*Encadrants :* Stefan Balev, Eric Sanlaville
Les graphes temporels (ou dynamiques) sont une extension des graphes classiques qui, comme leur nom l'indique, évoluent dans le temps. Parmi les différentes définitions possibles, nous retenons la suivante : nous avons un ensemble fixe de sommets et du temps discret. À chaque pas de temps, une arrête peut être présente ou pas.
Il y a deux façons de représenter un graphe temporel : comme une séquence de graphes dont chaque élément correspond à un pas de temps ou bien comme un seul graphe dans lequel les arêtes sont étiquetées avec leurs pas de présence.
Au sein de l'équipe RI2C du LITIS, beaucoup de travaux de recherche portent sur les graphes temporels.
La notion de connexité dans les graphes temporels est plus subtile que dans les graphes classiques. Elle peut être basée sur connexité instantanée (deux sommets u et v sont connectés s'il existe un chemin entre eux à chaque pas de temps) ou alors sur des trajets temporels (on peut partir du premier sommet, traverser une arête à chaque pas de temps et arriver dans le second). Dans ce dernier cas, la relation n'est pas forcement symétrique.
Au sein de l'équipe RI2C du LITIS, beaucoup de travaux de recherche portent sur les graphes temporels. Nous avons conçu et analysé théoriquement certains algorithmes de résolution de problèmes de connexité.
Le but principal de ce projet est d'implanter ces algorithmes avec une attention particulière à leurs performances et de les analyser expérimentalement afin e confirmer les prédictions théoriques. Le deuxième but est de réfléchir sur (et éventuellement proposer des solutions à) certains problèmes de connexité encore ouvertes.
*Technologies :* Java, GraphStream