著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.

Modern embedded processors with dedicated address generation unit support memory accesses using indirect addressing mode with auto-increment and auto-decrement. The auto-increment/decrement mode, if properly utilized, can save address arithmetic instructions, reduce static and dynamic footprint of the program and speed up the execution as well. We propose an optimization framework for embedded processors based on the auto-increment and decrement addressing modes for address registers. Existing work on this class of optimizations focuses on using an access graph and finding the maximum weight path cover to find an optimized stack variables layout. We take this further by using coalescing, addressing mode selection and offset registers to find further opportunities for reducing the number of load-address instructions required. We also propose an algorithm for building the layout with considerations for memory accesses across basic blocks, because existing work mainly considers intra-basic-block information. We then use the available offset registers to try to further reduce the number of address arithmetic instructions after layout assignment.

In this work we provide several improvements in the study of phase transitions of interacting particle systems: - We determine a quantitative relation between non-extremality of the limiting Gibbs measure of a tree-based spin system, and the temporal mixing of the Glauber Dynamics over its finite projections. We define the concept of 'sensitivity' of a reconstruction scheme to establish such a relation. In particular, we focus on the independent sets model, determining a phase transition for the mixing time of the Glauber dynamics at the same location of the extremality threshold of the simple invariant Gibbs version of the model. - We develop the technical analysis of the so-called spatial mixing conditions for interacting particle systems to account for the connectivity structure of the underlying graph. This analysis leads to improvements regarding the location of the uniqueness/non-uniqueness phase transition for the independent sets model over amenable graphs; among them, the elusive hard-square model in lattice statistics, which has received attention since Baxter's solution of the analogous hard-hexagon in 1980. - We build on the work of Montanari and Gerschenfeld to determine the existence of correlations for the coloring model in sparse random graphs. In particular, we prove that correlations exist above the 'clustering' threshold of such a model; thus providing further evidence for the conjectural algorithmic 'hardness' occurring at such a point.

- / -

In this work, regression models for the wake field entering a propeller at certain axial andnominal position have been proposed. Wakes are non-uniform flows following a body immersedin a viscous fluid. We have proposed models for the axial and tangential velocity distribution asfunctions of ship hull and propeller measures. The regression models were modelled using Fourierseries and parameter estimations based on skewed-Gaussian and sine functions. The wake fieldis an important parameter in propeller design. The regression models are based on experimentaldata provided by the Rolls-Royce Hydrodynamic Research Center in Kristinehamn. Also we havestudied the flow in the axial velocity distribution in the propeller plane using the coherent structurecoloring method. The coherent structure coloring is used to study coherent patterns by looking atfluid particle kinematics. Using this type of analysis, we observed that the velocity distributionbehaves kinematically similar in the different regions of the wake distribution, which according tothe coherent structure coloring indicate coherence. / I det här arbetet, har regressionsmodeller för medströmsfältet in i en propeller vid viss axielloch nominell position utvecklats. Medströmsfältet är ojämn strömning efter en kropp nedsänkt i enviskös vätska. Vi har föreslagit modeller för axiell och tangentiell hastighetsfördelning som funktionerför fartygsskrov-och propeller-parametrar. Regressionsmodellerna modellerades med hjälpav Fourier-serier och parameterskattning baserade på skeva Gaussfördelningar och sinusfunktioner.Medströmsfältet är en viktig parameter i propeller design. Regressionsmodellerna är baserade påexperimentella data från Rolls-Royces Hydrodynamiska Forskningscenter i Kristinehamn. Vi harockså studerat flödet i axialhastighetsfördelningen i propellplanet med hjälp av den koherenta struktureringsfärgmetoden.Den koherenta struktureringsfärgmetoden används för att studera koherentamönster genom att titta på vätskepartikelkinematik. Med hjälp av denna typ av analys observeradevi att hastighetsfördelningen uppför sig kinematiskt lika i de olika regionerna i medströmsfältet,vilket enligt koherenta strukturfärgmetoden indikerar koherens.

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elleest constitué de trois grandes parties, la première est consacrée à l’étude d’unnouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantespar écarte. Il consiste de trouver une valuation des arêtes qui permettede distinguer les sommets de graphes telle que chaque sommet v du graphe est identifiéde façon unique par la différence entre la plus grande et la plus petite des valeursincidentes à v. Le plus entier pour lequel le graphe G admet une arête-colorationsommets-distinguantes par écarte est le nombre chromatique par écart de G, notégap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Uneconjecture intéressante, proposée dans cette partie, suggère que le nombre chromatiquepar écart de tout graphe connexe d’ordre n > 2 vaut n - 1, n ou n + 1.La deuxième partie du manuscrit concerne le problème du placement de graphes.Nous proposons un état de l’art des problèmes de placement de graphes, puis nousintroduisons la nouvelle notion de placement de graphes étiquetés. Il s’agit d’unplacement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposonsdes encadrements de ce nouveau paramètre pour plusieurs classes de graphes.La troisième partie de la thèse s’intéresse au problème d’appariement d’arbres dansle cadre de la recherche d’information dans des documents structurés de type XML.Les algorithmes holistique de jointure structurelle est l’une des premières méthodesproposées pour résoudre l’appariement exact des documents XML. Ces algorithmessont souvent divisés en deux grandes étapes. La première étape permet de décomposerl’arbre de la requête en un ensemble de petites composantes connexes. Ensuite,des solutions intermédiaires pour chaque composante de la requête sont trouvées, cesrésultats intermédiaires sont joints pour obtenir la solution finale. Nous proposonsdans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalementà diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithmeobtient de meilleurs résultats en comparaison avec deux autres méthodes de l’étatde l’art. / In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Cette thèse s'intéresse à différents types d'interactions entre les cliques et les stables, deux objets très importants en théorie des graphes, ainsi qu'aux relations entre ces différentes interactions. En premier lieu, nous nous intéressons au problème classique de coloration de graphes, qui peut s'exprimer comme une partition des sommets du graphe en stables. Nous présentons un résultat de coloration pour les graphes sans triangles ni cycles pairs de longueur au moins 6. Dans un deuxième temps, nous prouvons la propriété d'Erdös-Hajnal, qui affirme que la taille maximale d'une clique ou d'un stable devient polynomiale (contre logarithmique dans les graphes aléatoires) dans le cas des graphes sans chemin induit à k sommets ni son complémentaire, quel que soit k.Enfin, un problème moins connu est la Clique-Stable séparation, où l'on cherche un ensemble de coupes permettant de séparer toute clique de tout stable. Cette notion a été introduite par Yannakakis lors de l’étude des formulations étendues du polytope des stables dans un graphe parfait. Il prouve qu’il existe toujours un séparateur Clique-Stable de taille quasi-polynomiale, et se demande si l'on peut se limiter à une taille polynomiale. Göös a récemment fourni une réponse négative, mais la question se pose encore pour des classes de graphes restreintes, en particulier pour les graphes parfaits. Nous prouvons une borne polynomiale pour la Clique-Stable séparation dans les graphes aléatoires et dans plusieurs classes héréditaires, en utilisant notamment des outils communs à l'étude de la conjecture d'Erdös-Hajnal. Nous décrivons également une équivalence entre la Clique-Stable séparation et deux autres problèmes  : la conjecture d'Alon-Saks-Seymour généralisée et le Problème Têtu, un problème de Satisfaction de Contraintes. / This thesis is concerned with different types of interactions between cliques and stable sets, two very important objects in graph theory, as well as with the connections between these interactions. At first, we study the classical problem of graph coloring, which can be stated in terms of partioning the vertices of the graph into stable sets. We present a coloring result for graphs with no triangle and no induced cycle of even length at least six. Secondly, we study the Erdös-Hajnal property, which asserts that the maximum size of a clique or a stable set is polynomial (instead of logarithmic in random graphs). We prove that the property holds for graphs with no induced path on k vertices and its complement.Then, we study the Clique-Stable Set Separation, which is a less known problem. The question is about the order of magnitude of the number of cuts needed to separate all the cliques from all the stable sets. This notion was introduced by Yannakakis when he studied extended formulations of the stable set polytope in perfect graphs. He proved that a quasi-polynomial number of cuts is always enough, and he asked if a polynomial number of cuts could suffice. Göös has just given a negative answer, but the question is open for restricted classes of graphs, in particular for perfect graphs. We prove that a polynomial number of cuts is enough for random graphs, and in several hereditary classes. To this end, some tools developed in the study of the Erdös-Hajnal property appear to be very helpful. We also establish the equivalence between the Clique-Stable set Separation problem and two other statements: the generalized Alon-Saks-Seymour conjecture and the Stubborn Problem, a Constraint Satisfaction Problem.

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.<p><p>La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.<p><p>Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The aim of this study was to explore the effect a coloring condition had on minimizing anxiety and stress experienced daily by veterans. The effect that coloring had on working memory was also explored. A sample of 24 armed forces veterans were split into two coloring conditions, a mandala and a free draw condition, and asked to complete the Primary Care PTSD Screen, the Perceived Stress Scale and the Brief State Trait Anxiety Inventory. Working memory scores were established via a Backward Digit Recall task; pre-and posttest scores were evaluated for significant differences. Our research suggests the act of coloring, not the coloring condition, resulted in significant decreases in stress and anxiety and an increase in working memory. We also found that participants who suffer from PTSD displayed significant decreases in stress and anxiety and significant increases in working memory when compared to individuals without PTSD.

Hypergraph partitioning lies at the heart of a number of problems in machine learning as well as other engineering disciplines. While partitioning uniform hypergraphs is often required in computer vision problems that involve multi-way similarities, non-uniform hypergraph partitioning has applications in database systems, circuit design etc. As in the case of graphs, it is known that for given objective and balance constraints, the problem of optimally partitioning a hypergraph is NP-hard. Yet, over the last two decades, several efficient heuristics have been studied in the literature and their empirical success is widely appreciated. In contrast to the extensive studies related to graph partitioning, the theoretical guarantees of hypergraph partitioning approaches have not received much attention in the literature. The purpose of this thesis is to establish the statistical error bounds for certain spectral algorithms for partitioning uniform as well as non-uniform hypergraphs. The mathematical framework considered in this thesis is the following. Let V be a set of n vertices, and ψ : V ->{1,…,k} be a (hidden) partition of V into k classes. A random hypergraph (V,E) is generated according to a planted partition model, i.e., subsets of V are independently added to the edge set E with probabilities depending on the class memberships of the participating vertices. Let ψ' be the partition of V obtained from a certain algorithm acting on a random realization of the hypergraph. We provide an upper bound on the number of disagreements between ψ and ψ'. To be precise, we show that under certain conditions, the asymptotic error is o(n) with probability (1-o(1)). In the existing literature, such error rates are only known in the case of graphs (Rohe et al., Ann. Statist., 2011; Lei \& Rinaldo, Ann. Statist., 2015), where the planted model coincides with the popular stochastic block model. Our results are based on matrix concentration inequalities and perturbation bounds, and the derived bounds can be used to comment on the consistency of spectral hypergraph partitioning algorithms. It is quite common in the literature to resort to a spectral approach when the quantity of interest is a matrix, for instance, the adjacency or Laplacian matrix for graph partitioning. This is certainly not true for hypergraph partitioning as the adjacency relations cannot be encoded into a symmetric matrix as in the case of graphs. However, if one restricts the problem to m-uniform hypergraphs for some m ≥ 2, then a symmetric tensor of order m can be used to express the multi-way interactions or adjacencies. Thus, the use of tensor spectral algorithms, based on the spectral theory of symmetric tensors, is a natural choice in this scenario. We observe that a wide variety of uniform hypergraph partitioning methods studied in the literature can be related to any one of two principle approaches: (1) solving a tensor trace maximization problem, or (2) use of the higher order singular value decomposition of tensors. We derive statistical error bounds to show that both these approaches lead to consistent partitioning algorithms. Our results also hold when the hypergraph under consideration allows weighted edges, a situation that is commonly encountered in computer vision applications such as motion segmentation, image registration etc. In spite of the theoretical guarantees, a tensor spectral approach is not preferable in this setting due to the time and space complexity of computing the weighted adjacency tensor. Keeping this practical scenario in mind, we prove that consistency can still be achieved by incorporating certain tensor sampling strategies. In particular, we show that if the edges are sampled according to certain distribution, then consistent partitioning can be achieved with only few sampled edges. Experiments on benchmark problems demonstrate that such sampled tensor spectral algorithms are indeed useful in practice. While vision tasks mostly involve uniform hypergraphs, in database and electronics applications, one often finds non-uniform hypergraphs with edges of varying sizes. These hypergraphs cannot be expressed in terms of adjacency matrices or tensors, and hence, use of a spectral approach is tricky in this context. The partitioning problem gets more challenging due to the fact that, in practice, these hypergraphs are quite sparse, and hence, provide less information about the partition. We consider spectral algorithms for partitioning clique and star expansions of hypergraphs, and study their consistency under a sparse planted partition model. The results of hypergraph partitioning can be further extended to address the well-known hypergraph vertex coloring problem, where the objective is to color the vertices such that no edge is monochromatic. The hardness of this problem is well established. In fact, even when a hypergraph is bipartite or 2-colorable, it is NP-hard to find a proper 2-coloring for it. We propose a spectral coloring algorithm, and show that if the non-monochromatic subsets of vertices are independently added to the edge set with certain probabilities, then with probability (1-o(1)), our algorithm succeeds in coloring bipartite hypergraphs with only two colors. To the best our knowledge, these are the first known results related to consistency of partitioning general hypergraphs.