Modèles et algorithmes pour les graphes dynamiques Models and alorithms for dynamic graphs Fr En

Fiche du document

Date

19 octobre 2020

Périmètre
Langue
Identifiant
Source

Theses.fr

Collection

Theses.fr

Organisation

ABES

Licences

Open Access , http://purl.org/eprint/accessRights/OpenAccess


Mots-clés

Graphe dynamique Algorithme exact Modélisation Problème de flot Connexité Dynamic graph Exact algorithm Model Flow problem Connectivity


Citer ce document

Mathilde Vernet, « Modèles et algorithmes pour les graphes dynamiques », Theses.fr, ID : 10670/1.5uhaig


Métriques


Partage / Export

Résumé Fr En

Les problèmes de graphes ont été largement étudiés dans le cas des graphes statiques. Cependant, ces graphes ne permettent pas de prendre en compte la dimension temporelle, qui est souvent une donnée importante pour les situations à modéliser. Les graphes dynamiques viennent combler ces lacunes en permettant de modéliser des évolutions dans le temps. On peut alors s'interroger sur ces mêmes problèmes de graphes dans un contexte dynamique. Cela passe d'abord par la définition du modèle de graphes dynamiques le plus approprié et la modélisation précise du problème sur ces graphes. Lorsque le problème ne peut pas être résolu efficacement en appliquant directement des méthodes connues sur les graphes statiques, il faut alors concevoir un algorithme de résolution spécifique aux graphes dynamiques et l'analyser théoriquement et expérimentalement.En suivant cette démarche, l'objectif de cette thèse est de s'interroger sur l'extension aux graphes dynamiques des problèmes bien connus sur les graphes statiques. Ce travail s'intéresse à plusieurs problèmes de graphes en contexte dynamique en se focalisant sur les aspects algorithmiques et en s'abstrayant des domaines d'applications.

Graph problems have been widely studied in the case of static graphs. However, these graphs do not allow a time dimension to be considered, even though time is an important variable for the situations to model. Dynamic graphs make it possible to model evolution over time. This is a reason to wonder about graph problems in a dynamic context. First, it is necessary to define the most appropriate dynamic graphs model and the precise problem on those graphs. When the problem cannot be efficiently solved directly using known static graph methods, an algorithm specific to dynamic graphs must be designed and analyzed theoretically and practically.With that approach, this thesis' objective is to study graph problems' extensions to dynamic graphs. This works deals with several graph problems in a dynamic context by focusing on algorithmic aspects and without considering application domains.

document thumbnail

Par les mêmes auteurs

Sur les mêmes sujets

Exporter en