Cette thèse porte sur l'étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d'optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d'autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d'un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l'écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l'étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d'approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d'infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes.

Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.

Romancier reconnu de son vivant, Louis Guilloux n’a néanmoins pas accédé au statut de grand écrivain. Nous voudrions mettre ici en valeur la diversité des formes littéraires exploitées par le romancier, en proposant un parcours générique et diachronique de son œuvre, à partir du Sang noir. L’approche poétique de ses récits sera ancrée dans l’histoire des idées et des représentations. Nous souhaiterions également éclairer les choix esthétiques de Louis Guilloux par les stratégies de positionnement qu’il a adoptées pour renforcer sa place dans le champ littéraire. Nous nous appuierons sur des documents d’archives pour mieux comprendre le geste littéraire de l’écrivain et sa conception du roman. Louis Guilloux s’est distingué par Le Sang noir avec lequel il a renouvelé l’horizon d’attente de la littérature de guerre. Il n’a cessé par la suite d’interroger les rapports entre la fiction et l’Histoire, en problématisant leurs frontières et en s’essayant à des genres en marge du roman, le témoignage et le reportage. Néanmoins, à partir des années cinquante, son œuvre et sa carrière prennent un nouveau tournant. Alors qu’il entre dans une phase de consécration, il aspire à renouveler fondamentalement son art. Les modalités de son engagement politique changent également : il soutient la diffusion de la culture. Louis Guilloux rompt avec son univers romanesque et se réapproprie les codes de la littérature d’évasion. Il s’engage par ailleurs dans un ultime projet autobiographique dans lequel il propose une dernière variation romanesque de son parcours. L’œuvre de Louis Guilloux illustre ainsi une exploration foisonnante du genre romanesque. Elle recouvre également de nombreuses tensions qu’il s’agira d’éclairer. / Although Louis Guilloux was a recognized novelist in his lifetime, he was never considered as a major writer. The purpose of my thesis is to emphasize the diversity of the literary forms he used and to offer a generic as well as a diachronic reading of his work, starting from Le Sang noir. The poetical approach to his narratives will be grounded in the history of ideas and representations. Guilloux’s aesthetic choices will also be discussed in the light of the positioning strategies he adopted to carve out a place for himself in the literary world. Archival documents will be a starting point for a better understanding of the writers’s literary achievements and his conception of the novel. Louis Guilloux became famous for Le Sang noir, which created new expectations for war literature. Subsequently, he ceaselessly explored the link between fiction and history, looking at their dividing line and trying his hand at accounts and reports, two genres close to the novel. However, in the 1950s, he came to a turning point both in his career and his work. Even as he was consecrated as a writer, he became eager to renew his art completely. His political commitment also changed in its form as he now supported the diffusion of culture. Guilloux broke away from the world of his novels and appropriated the codes of escapist literature. Moreover he launched into his last autobiographical attempt, in which he offered one ultimate novelistic variation on his progress. Louis Guilloux’s work thus exemplifies a rich exploration of the novel as a genre. It is also fraught with numerous tensions that will have to be clarified.