Show simple item record

Optimization problems with propagation in graphs : Parameterized complexity and approximation

dc.contributor.advisorBazgan, Cristina
dc.contributor.authorChopin, Morgan*
dc.date.accessioned2014-01-27T14:42:29Z
dc.date.available2014-01-27T14:42:29Z
dc.date.issued2013-07
dc.identifierhttp://basepub.dauphine.fr/theses/2013PA090023
dc.identifier
dc.identifierhttp://tel.archives-ouvertes.fr/tel-00933769
dc.identifierhttp://www.theses.fr/2013PA090023
dc.identifier2013PA090023
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12520
dc.description.abstractfrDans 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
dc.language.isoenen
dc.subjectOptimisation combinatoireen
dc.subjectThéorie des graphesen
dc.subjectAlgorithmes d'approximationen
dc.subjectComplexité paramétréeen
dc.subjectApproximation paramétréeen
dc.subjectRéseaux sociauxen
dc.subjectProblème du pompieren
dc.subjectSelection d'un ensemble cibleen
dc.subjectCombinatorial optimizationen
dc.subjectGraph theoryen
dc.subjectApproximation algorithmsen
dc.subjectParameterized complexityen
dc.subjectParameterized approximationen
dc.subjectSocial networksen
dc.subjectFirefighter problemen
dc.subjectTarget set selectionen
dc.subject.ddc003en
dc.titleProblèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximationfr
dc.titleOptimization problems with propagation in graphs : Parameterized complexity and approximationen
dc.typeThèseen
dc.subject.classificationrameauOptimisation combinatoire
dc.subject.classificationrameauAlgorithmes d'approximation
dc.subject.classificationrameauRéseaux sociaux
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenIn 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.en
dc.identifier.citationpages136en
dc.identifier.theseid2013PA090023en
dc.subject.ddclabelRecherche opérationnelleen
dc.rights.intranetnonen
hal.person.labIds*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record