en fr Optimization problems with propagation in graphs : Parameterized complexity and approximation Problèmes doptimisation avec propagation dans les graphes : complexité paramétrée et approximation Reportar como inadecuado




en fr Optimization problems with propagation in graphs : Parameterized complexity and approximation Problèmes doptimisation avec propagation dans les graphes : complexité paramétrée et approximation - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LAMSADE - Laboratoire d-analyse et modélisation de systèmes pour l-aide à la décision

Abstract : In this thesis, we investigate the computational complexity of optimization problems involving a -diffusion process- in a graph. More specifically, we are first interested to the target set selection problem. This problem consists of finding the smallest set of initially -activated- vertices of a graph such that all the other vertices become activated after a finite number of propagation steps. If we modify this process by allowing the possibility of ``protecting- a vertex at each step, we end up with the firefighter problem that asks for minimizing the total number of activated vertices by protecting some particular vertices. In fact, we introduce and study a generalized version of this problem where more than one vertex can be protected at each step. We propose several complexity results for these problems from an approximation point of view and a parameterized complexity perspective according to standard parameterizations as well as parameters related to the graph structure.

Résumé : Dans cette thèse, nous étudions la complexité algorithmique de problèmes d-optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d-abord au problème de sélection d-un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d-un graphe à -activer- au départ tel que tous les autres sommets soient activés après un nombre fini d-étapes de propagation. Si nous modifions ce processus en permettant de -protéger- un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d-un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l-approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.

en fr

Keywords : Combinatorial optimization Graph theory Approximation algorithms Parameterized complexity Parameterized approximation Social networks Firefighter problem Target set selection

Mots-clés : Optimisation combinatoire Théorie des graphes Algorithmes d-approximation Complexité paramétrée Approximation paramétrée Réseaux sociaux Problème du pompier Selection d-un ensemble cible





Autor: Morgan Chopin -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados