Tester efficacement la T-intervalle connexité dans les graphes dynamiques

Beaucoup de reseaux dynamiques sont constitues d'entites durables dont les liens evoluent a travers le temps. D'un point de vue global et discret, ces reseaux se modelisent bien sous forme d'un graphe evolutif, c'est a dire une suite de graphes G = {G 1 , G 2 , ..., G δ } telle que G i = (V, E i) represente la topologie du reseau pendant la periode i. Une telle suite est dite T-intervalle connexe si pour tout t ∈ [1, δ − T + 1] les graphes G t , G t+1 , ..., G t+T −1 partagent un meme sous-graphe couvrant connexe. Dans cet article, nous etudions le probleme de decider si une suite G donnee est T-intervalle connexe pour un T donne. Nous etudions egalement la variante ou T n'est pas donne et il s'agit de trouver le plus grand T tel que G est T-intervalle connexe. Nous supposons que les changements entre deux graphes consecutifs sont arbitraires, et que deux operations (intersection binaire et test de connexite) sont utilisees comme briques de base. Nous montrons que Ω(δ) de ces operations sont necessaires pour les deux variantes et presentons des solutions qui en utilisent O(δ) egalement. Ces solutions sont donc optimales a une constante multiplicative pres.