Entrepôts, Représentation et Ingénierie des Connaissances
Publications du laboratoire

Recherche approfondie

par Année
par Auteur
par Thème
par Type
--------------------
- Forte ∆-connexité dans les flots de liens hal link

Auteur(s): Huyghues-Despointes C., Bui-Xuan Binh-Minh, Magnien Clémence

Conference: ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (Bayonne, FR, 2016-05-24)
Actes de conférence: ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, vol. p. ()


Ref HAL: hal-01305128_v1
Résumé:

Les flots de liens modélisent les interactions temporelles et sont constitués de paires (t, uv) représentant un lien entre les sommets u et v au temps t. La question de la connexité est plus difficile dans le cas des flots de liens que dans le cas des graphes, car la relation d'accessibilité n'est pas transitive. Nous etudions la notion de composante fortement ∆-connexe dans les flots de liens (ou les graphes evolutifs). Le calcul exact des composantes fortement ∆-connexes etant NP-difficile, nous proposons un algorithme qui donne une borne supérieure et une borne inférieure de la taille de la plus grande composante.