A Unifying Model for Representing Time-Varying Graphs

Klaus Wehmuth 1 Artur Ziviani 1, * Eric Fleury 2, *
* Auteur correspondant
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Résumé : Nous proposons un modèle (TVG pour \emph{Time-Varying Graphs}) pour représenter les graphes dynamiques (\emph{i.e.}, des graphes susceptibles d'évoluer au cours du temps). Nous montrons qu elles définitionsclefs comme le degré, la notion de chemin, de connectivité sont prise en compte par ce modèle. Une analyse de la complexité des structures de données nécessaire à la représentation de ce modèle montre que la complexité asymptotique est en $O(m)$ (cardinalité du nombre d'arêtes du graphe dynamique). Si les sommets d'un TVG peuvent être considérés comme des entités indépendantes à chaque instant, alors on démontre que le graphe TVG est isomorphe à un graphe orienté static. Notre modèle permet de représenter et de prendre en compte les différentes propositions existantes qui n'étaient pas en mesure de se représenter les unes les autres.
Type de document :
Rapport
[Research Report] RR-8466, INRIA. 2014, pp.38
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00941622
Contributeur : Eric Fleury <>
Soumis le : vendredi 14 février 2014 - 09:34:18
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : dimanche 9 avril 2017 - 10:48:20

Fichiers

RR-8466.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00941622, version 2
  • ARXIV : 1402.3488

Citation

Klaus Wehmuth, Artur Ziviani, Eric Fleury. A Unifying Model for Representing Time-Varying Graphs. [Research Report] RR-8466, INRIA. 2014, pp.38. 〈hal-00941622v2〉

Partager

Métriques

Consultations de la notice

618

Téléchargements de fichiers

381