No description available.

This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.

After recognizing the beauty and the utility of Graph Theory in solving a variety of problems, the author decided that it would be a good idea to make the subject available for students earlier in their educational experience. In this thesis, the author developed four units in Graph Theory, namely Vertex Coloring, Minimum Spanning Tree, Domination, and Hamiltonian Paths and Cycles, which are appropriate for high school level.

Large-scale graph-structured datasets are growing at an increasing rate. Social network graphs are an example of these datasets. Processing large-scale graphstructured datasets are central to many applications ranging from telecommunication to biology and has led to the development of many parallel graph algorithms. Performance of parallel graph algorithms largely depends on how the underlying graph is partitioned. In this work, we focus on studying streaming vertex-cut graph partitioning algorithms where partitioners receive a graph as a stream of vertices and edges and assign partitions to them on their arrival once and for all. Some of these algorithms maintain a state during partitioning. In some cases, the size of the state is so huge that it cannot be kept in a single machine memory. In many real world scenarios, several instances of a streaming graph partitioning algorithm are run simultaneously to improve the system throughput. However, running several instances of a partitioner drops the partitioning quality considerably due to the incomplete information of partitioners. Even frequently sharing states and its combination with buffering mechanisms does not completely solves the problem because of the heavy communication overhead produced by partitioners. In this thesis, we propose an algorithm which tackles the problem of low scalability and performance of existing streaming graph partitioning algorithms by providing an efficient way of sharing states and its combination with windowing mechanism. We compare state-of-the-art streaming graph partitioning algorithms with our proposed solution concerning performance and efficiency. Our solution combines a batch processing method with a shared-state mechanism to achieve both an outstanding performance and a high partitioning quality. Shared state mechanism is used for sharing states of partitioners. We provide a robust implementation of our method in a PowerGraph framework. Furthermore, we empirically evaluate the impact of partitioning quality on how graph algorithms perform in a real cloud environment. The results show that our proposed method outperforms other algorithms in terms of partitioning quality and resource consumption and improves partitioning time considerably. On average our method improves partitioning time by 23%, decreases communication load by 15% and increase memory consumption by only 5% compared to the state-of-the-art streaming graph partitioning.

Ce travail est consacré à l'étude de faisabilité d'une imagerie par reconstruction de vertex (IRV) pour le contrôle qualité en temps réel de la thérapie par faisceau d'ions carbone. La détection de vertex d'interactions nucléaires repose sur la détection de particules secondaires : grâce à un dispositif de détection spatiale des fragments chargés (tracker), on peut reconstruire les trajectoires des particules émergeant du patient et les extrapoler jusqu'à leur point d'origine (le vertex)... Dans le cadre de notre étude, la position du vertex est déterminée de deux manières différentes : soit en calculant l'intersection de la trajectoire d'un fragment émergent avec celle de l'ion incident (connue grâce à l'utilisation d'un hodoscope de faisceau placé en amont du patient), soit grâce à l'intersection de la trajectoire de deux fragments émergents détectés en coïncidence. Notre étude de faisabilité de la technique repose sur l'outil de simulation GEANT4. La première partie de l'étude a consisté à valider cet outil grâce à plusieurs expériences réalisées au GANIL (Caen) et au GSI (Darmstadt) avec des ions carbone de différentes énergies dans des cibles d'eau ou de PMMA Par la suite, la comparaison des deux modes de détection des particules secondaires a montré que la technique utilisant l'hodoscope est la plus performante. Enfin, après l'optimisation des principaux paramètres de cette technique, une simulation réaliste montre qu'il est possible de mesurer le parcours des ions avec une précision millimétrique à l'échelle d'une tranche en énergie voire à l'échelle d'un voxel unique.

Cette thèse s'inscrit dans le cadre général de la théorie des systèmes intégrables avec bords et le développement des structures algébriques associées. D'une part, nous nous attaquons au problème de la diagonalisation de l'hamiltonien du modèle XXZ avec bords non diagonaux. Nous exhibons les deux ensembles d'états propres et valeurs propres du modèle si les paramètres de bords satisfont deux conditions. D'autre part, nous introduisons un modèle de physique statistique que nous appelons le modèle face avec un bord réfléchissant. Nous calculons exactement sa fonction de partition et nous montrons que cette dernière se représente simplement sous la forme d'un unique déterminant matriciel. Nous montrons que ces deux problèmes sont reliés par la transformation vertex-face et exhibent une structure algébrique commune, l'algèbre de réflexion dynamique. Nous nous intéressons aux aspects mathématiques de cette algèbre dans le cas elliptique général, et nous introduisons deux classes de ces représentations, la représentation de co-module d'évaluation et sa duale. Nous pensons que cette algèbre est la structure clef pour l'analyse des modèles faces avec bords. En particulier, nous montrons à l'aide de twists de Drinfel'd que leur fonction de partition se représente simplement dans le cas général.

<p>The main topic of this doctoral thesis is D-branes in string theory, expressed in the language of conformal field theory. The purpose of string theory is to describe the elementary particles and the fundamental interactions of nature, including gravitation as a quantum theory. String theory has not yet reached the status to make falsifiable predictions, thus it is not certain that string theory has any direct relevance to physics. On the other hand, string theory related research has led to progress in mathematics.</p><p>We begin with a short introduction to conformal field theory and some of its applications to string theory. We also introduce vertex algebras and discuss their relevance to conformal field theory. Some classes of conformal field theories are introduced, and we discuss the relevant vertex algebras, as well as their interpretation in terms of string theory.</p><p>In string theory, a D-brane specifies where the endpoint of the string lives. Many aspects of string theory can be described in terms of a conformal field theory, which is a field theory that lives on a two-dimensional space. The conformal field theory counterpart of a D-brane is a boundary state, which in some cases has a natural interpretation as constraining the string end point. The main focus of this thesis is on the interpretation of boundary states in terms of D-branes in curved target spaces.</p>

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

The main topic of this doctoral thesis is D-branes in string theory, expressed in the language of conformal field theory. The purpose of string theory is to describe the elementary particles and the fundamental interactions of nature, including gravitation as a quantum theory. String theory has not yet reached the status to make falsifiable predictions, thus it is not certain that string theory has any direct relevance to physics. On the other hand, string theory related research has led to progress in mathematics. We begin with a short introduction to conformal field theory and some of its applications to string theory. We also introduce vertex algebras and discuss their relevance to conformal field theory. Some classes of conformal field theories are introduced, and we discuss the relevant vertex algebras, as well as their interpretation in terms of string theory. In string theory, a D-brane specifies where the endpoint of the string lives. Many aspects of string theory can be described in terms of a conformal field theory, which is a field theory that lives on a two-dimensional space. The conformal field theory counterpart of a D-brane is a boundary state, which in some cases has a natural interpretation as constraining the string end point. The main focus of this thesis is on the interpretation of boundary states in terms of D-branes in curved target spaces.

My thesis fits into the domain of theoretical spectroscopy. This term describes a set of theoretical approaches that go hand-in-hand with several experimental techniques such as optical absorption and reflectivity, inelastic X-ray scattering (IXS), electron energy-loss spectroscopy (EELS) and photoelectron (or photoemission) spectroscopy. This set of ab-initio theories is used to simulate, study, predict and understand what is and will be seen in experiment. These spectroscopies are all connected to the dielectric function ε(ω ) of an electronic system which is, in fact, a fundamental quantity in many modern electronic structure theories. In particular I focused my research on photoemission spectroscopy, where the dielectric function enters as the screening of the hole due to the system. During my thesis I have worked on the development of new theoretical approaches, the aim of my project being to go beyond state-of-the-art methods used in electronic structure calculations. These methods stem mainly from two larger theoretical frameworks: Time-Dependent Density-functional Theory (TDDFT) and Green's function theory -- also known as Many-Body Perturbation Theory (MBPT). I carried on the theoretical development in parallel with numerical simulations on real materials and with experimental measurements, performed to verify the reliability of theory.