Dissertations / Theses on the topic 'Stable graph'

A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination number. In particular, we explore edge removal, edge addition, and vertex removal.

Random NP-Complete problems have come under study as an important tool used in the analysis of optimization algorithms and help in our understanding of how to properly address issues of computational intractability. In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as representative NP-Complete classes. Numerical evidence is presented for a phase transition in the probability of solution when a modified Lévy-Stable distribution is used in instance creation for each. Numerical evidence is presented that show hard random instances exist near the critical threshold for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s phase transition is also given. Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph ensemble presented is the first candidate, without specific graph structure built in, to generate graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from this distribution still show a phase transition and appear to have a pickup in search cost for the algorithms considered. Search cost is highly dependent on the particular algorithm used and the graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs that are difficult to test for Hamiltonicity. Number Partition Problem instances are created by choosing each element in the list from a modified Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable focus on pickup in search cost for the solvers used. The failure of current approximation algorithms and potential candidate approximation algorithms are discussed.

Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimaux
In this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching

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

Cette thèse traite de la coloration de graphe, de la coloration par liste,d'ensembles indépendants de poids maximum et de la théorie structurelle des graphes.Dans un premier temps, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème de la 4-coloration dans des sous-classes de graphe sans $P_6$. Ces algorithmes se basent sur une compréhension précise de la structure de ces classes de graphes, pour laquelle nous donnons une description complète.Deuxièmement, nous étudions une conjecture portant sur la coloration par liste et prouvons que pour tout graphe parfait sans griffe dont la taille de la plus grande clique est bornée par 4, le nombre chromatique est égal au nombre chromatique par liste. Ce résultat est obtenu en utilisant un théorème de décomposition des graphes parfaits sans griffe, une description structurelle des graphes de base de cette décomposition et le célèbre théorème de Galvin.Ensuite, en utilisant la description structurelle élaborée dans le premier chapitre et en renforçant certains aspects de celle-ci, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème d'indépendant de poids maximum dans des sous-classes de graphe sans $P_6$ et sans $P_7$. Dans le dernier chapitre de ce manuscrit, nous infirmons une conjecture datant de 1999 de De Simone et K"orner sur les graphes normaux. Notre preuve est probabiliste et est obtenue en utilisant les graphes aléatoires
This thesis deals with graph coloring, list-coloring, maximum weightstable set (shortened as MWSS) and structural graph theory.First, we provide polynomial-time algorithms for the 4-coloring problem insubclasses of $P_6$-free graphs. These algorithms rely on a preciseunderstanding of the structure of these classes of graphs for which we give afull description.Secondly, we study the list-coloring conjecture and prove that for anyclaw-free perfect graph with clique number bounded by 4, the chromatic numberand the choice number are equal. This result is obtained by using adecomposition theorem for claw-free perfect graphs, a structural description ofthe basic graphs of this decomposition and by using Galvin's famous theorem.Next by using the structural description given in the first chapter andstrengthening other aspects of this structure, we provide polynomial-timealgorithms for the MWSS problem in subclasses of $P_6$-free and $P_7$-freegraphs.In the last chapter of the manuscript, we disprove a conjecture of De Simoneand K"orner made in 1999 related to normal graphs. Our proof is probabilisticand is obtained by the use of random graphs

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA
In this thesis, we first present a study of several problems in the field of distributed algorithms. We provide a formal model that relies on anonymous networks. In this model, we characterize graphs in which it is possible to solve enumeration and leader election problems. This characterization is based on graph homomorphism. We introduce two algorithms with polynomial complexities that improve existing works with exponential complexities. On the other hand, we study the snapshot problem and we introduce the notion of weak snapshot. We show that there exist solutions for this problem in the context of anonymous networks. We present several results about distributed snapshots that deal with checkpoint and rollback recovery, termination detection or the cartography computation of a network. In a practical aspect, we present the conception, the development process and the implementation of these distributed snapshot algorithms within the simulation and visualization software ViSiDiA

We apply the semidefinite programming method to obtain a new upper bound on the cardinality of codes made of subspaces of a linear vector space over a finite field. Such codes are of interest in network coding.Next, with the same method, we prove an upper bound on the cardinality of sets avoiding one distance in the Johnson space, which is essentially Schrijver semidefinite program. This bound is used to improve existing results on the measurable chromatic number of the Euclidean space.We build a new hierarchy of semidefinite programs whose optimal values give upper bounds on the independence number of a graph. This hierarchy is based on matrices arising from simplicial complexes. We show some properties that our hierarchy shares with other classical ones. As an example, we show its application to the problem of determining the independence number of Paley graphs.

Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysés
The minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed

Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total domination number three and all total domination dot-stable graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

Neste projeto inicia-se o estudo de classificação de aplicações estáveis. Para isto usamos grafos que irão corresponder ao conjunto singular destas aplicações. Em um primeiro momento estudamos o caso de aplicações estáveis de superfícies no plano e depois estudamos aplicações estáveis de 3-variedades em \'R POT. 3\'
In this project we began the study of classification of stable maps. For this we use graphs that correspond to the singular set of these applications. At first we study the case of stable maps of surfaces in the plane and then we study stable maps of a 3-manifold in \'R POT. 3\'

Sont presentes des differents travaux ayant trait au probleme de l'independant de poids maximum. Il est decrit un algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans k::(1,3). Les graphes parfaits sont etudies. Un theoreme reduisant la h-perfection d'un graphe g a la h-perfection d'un sous-graphe propre de g est demontre. Il est presente une operation de reduction preservant la h-perfection. Un algorithme polynomial de reconnaissance des graphes sans k::(1,3) parfaits est propose. Presentation de cinq theoremes de decomposition des graphes parfaits en termes de p::(4)-structure

Submitted by Neusa Fagundes (neusa.fagundes@unioeste.br) on 2017-09-05T12:35:02Z No. of bitstreams: 1 Jianice_Frigo2017.pdf: 1119086 bytes, checksum: 87f159fe89d2840c9e6c7be155e2a65c (MD5)
Made available in DSpace on 2017-09-05T12:35:02Z (GMT). No. of bitstreams: 1 Jianice_Frigo2017.pdf: 1119086 bytes, checksum: 87f159fe89d2840c9e6c7be155e2a65c (MD5) Previous issue date: 2017-04-19
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
The infiltration process understanding and its relationship with soil properties is essential for the efficient management of soil and water. Thus, this paper aimed at evaluating water infiltration in an area of Oxisol, using single ring infiltrometers with different diameters. In addition, it also aimed at comparing the performance of 7 cm (A7) and 15 cm (A15) cylinders, matching soil moisture and bulk density to water infiltration and evaluating spatial distribution of infiltration. For this purpose, 24 data points were evaluated, placed in 8 plots of a circular area prepared for permaculture cropping, named as Mandala. Shewhart graphs and process capability index were used to compare cylinders and the inverse of distance square for data interpolation. It was observed that the average stable infiltration rate, determined with A7 cylinder, was 196.79 mm h-1 and with A15 cylinder was 187.30 mm h-1, consequently, there was a difference of 5.6%. The process capacity was estimated at 0.61 for A7 and 1.62 for A15, considered adequate for A15 and inadequate for A7 cylinder. Thus, it was concluded that the infiltration rates that were stabilized and determined by the cylinders were compatible with the rates determined by other methods in other papers. Regarding the performance of single-ring infiltrometers, it is concluded that, although both cylinders presented controlled processes, and did not differ statistically, cylinder A15 presented less variability on data, and may be considered adequate due to its process capability index.
O entendimento do processo de infiltração e das suas relações com as propriedades do solo é fundamental para o eficiente manejo do solo e da água. Assim, este trabalho teve como objetivo avaliar a infiltração de água em uma área de latossolo vermelho, para tanto, foram utilizados infiltrômetros de único cilindro, de diferentes diâmetros. Além disso, objetivou-se comparar o desempenho desses cilindros de 7 (A7) e de 15 cm (A15), relacionar a umidade e a densidade aparente do solo à infiltração da água e avaliar a distribuição espacial da infiltração. Foram avaliados 24 pontos de coleta de dados, alocados em 8 parcelas de um talhão circular preparado para plantio em regime de permacultura, denominado mandala. Gráficos de Shewhart e o índice de capacidade de processo foram utilizados para a comparação entre os cilindros e inverso do quadrado da distância para interpolação de dados. Verificou-se que a taxa de infiltração estável média, determinada com o cilindro A7, foi de 196,79 mm h-1 e com o cilindro A15 foi de 187,30 mm h-1, cuja diferença foi de 5,6 %. A capacidade de processo foi estimada em 0,61 para A7 e 1,62 para A15, a qual foi considerada adequada para o cilindro A15, porém inadequada para cilindro A7. Desta forma, neste trabalho, concluiu-se que as taxas de infiltração estáveis e determinadas pelos cilindros foram compatíveis com as taxas determinadas por outros métodos em outros trabalhos. Em relação ao desempenho dos infiltrômetros de cilindros únicos, conclui-se que, embora ambos os cilindros tenham apresentado processos controlados e não tenham diferido estatisticamente, o cilindro A15 apresentou menos variabilidade dos dados, e pode ser considerado adequado em função do seu índice de capacidade de processo.

L'objectif de cette thèse est de réussir à utiliser des décompositions de graphes afin de résoudre des problèmes algorithmiques sur les graphes. Notre objet d'étude principal est la classe des graphes de Berge apprivoisés. Les graphes de Berge sont les graphes ne possédant ni cycle de longueur impaire supérieur à 4 ni complémentaire de cycle de longueur impaire supérieure à 4. Dans les années 60, Claude Berge a conjecturé que les graphes de Berge étaient des graphes parfaits. C'est-à-dire que la taille de la plus grande clique est exactement le nombre minimum de couleurs nécessaire à une coloration propre et ce pour tout sous-graphe. En 2002, Chudnovsky, Robertson, Seymour et Thomas ont démontré cette conjecture en utilisant un théorème de structure: les graphes de Berge sont basiques ou admettent une décomposition. Ce résultat est très utile pour faire des preuves par induction. Cependant, une des décompositions du théorème, la skew-partition équilibrée, est très difficile à utiliser algorithmiquement. Nous nous focalisons donc sur les graphes de Berge apprivoisés, c'est-à-dire les graphes de Berge sans skew-partition équilibrée. Pour pouvoir faire des inductions, nous devons adapter le théorème destructure de Chudnovsky et al à notre classe. Nous prouvons un résultat plus fort: les graphes de Berge apprivoisés sont basiques ou admettent une décomposition telle qu'un côté de la décomposition soit toujours basique. Nous avons de plus un algorithme calculant cette décomposition. Nous utilisons ensuite notre théorème pour montrer que les graphes de Berge apprivoisés admettent la propriété du grand biparti, de la clique-stable séparation et qu'il existe un algorithme polynomial permettant de calculer le stable maximum
The goal of this these is to use graph's decompositions to solve algorithmic problems on graphs. We will study the class of Berge tame graphs. A Berge graph is a graph without cycle of odd length at least 4 nor complement of cycle of odd length at least 4.In the 60's, Claude Berge conjectured that Berge graphs are perfect graphs. The size of the biggest clique is exactly the number of colors required to color the graph. In 2002, Chudnovsky, Robertson, Seymour et Thomas proved this conjecture using a theorem of decomposition: Berge graphs are either basic or have a decomposition. This is a useful result to do proof by induction. Unfortunately, one of the decomposition, the skew-partition, is really hard to use. We arefocusing here on Berge tame graphs, i.e~Berge graph without balanced skew-partition. To be able to do induction, we must first adapt the Chudnovsky et al's theorem of structure to our class. We prove a stronger result: Berge tame graphs are basic or have a decomposition such that one side is always basic. We also have an algorithm to compute this decomposition. We then use our theorem to prouve that Berge tame graphs have the big-bipartite property, the clique-stable set separation property and there exists a polytime algorithm to compute the maximum stable set

O objetivo desta dissertação é estudar grafos com pesos nos vértices como um invariante global das aplicações de Gauss estáveis de superfícies compactas e orientadas. Apresentaremos também alguns invariantes locais que são importantes no estudo de aplicações estáveis. Abordaremos o problema de realização de grafos por aplicações de Gauss estáveis, considerando também um destes invariantes, o número de cúspides destas aplicações. Finalmente, usaremos matrizes para representar estes invariantes e definiremos classes de equivalências para estes representantes. Esta foi uma ideia que surgiu no final deste trabalho de mestrado.
The propose of this work is to study graphs with weights at the vertices as a global invariant of stable Gauss applications on compact and oriented surfaces. We also present some local invariants that are important to the study of stable applications. We approach the problem of realization of graphs by stable Gauss applications, also emphasizing one of these invariants, the number of cusps of these applications. Finally, we use matrices to represent these invariants and define equivalence classes for these representatives. This idea appeared at the end of this master\'s thesis.

Cette thèse porte sur la théorie des graphes, des hypergraphes, et des treillis. Nous nous intéressons à la complexité du problème de dualisation des fonctions monotones Booléennes, ainsi qu’à ses généralisations, à travers les différentes formes qu’il prend dans ces structures: énumération des dominants minimaux, des transversaux minimaux, dualisation dans les treillis, et énumération des éléments meet-irréductibles. De nouveaux résultats positifs et négatifs sont obtenus, et des directions de recherche futures sont proposées. La thèse se découpe comme suit. Dans une première partie, nous nous intéressons à l’énumération des dominants minimaux dans les graphes. Nous obtenons de nouveaux algorithmes output-polynomiaux dans les graphes sans grande clique, et dans d’autres classes de graphes liées aux ordres partiels de dimension bornée. Dans une seconde partie, nous nous intéressons aux généralisations de ce problème dans les treillis. Une première généralisation concerne la dualisation dans les treillis donnés par une base d’implications, l’autre concerne l’énumération des éléments meet-irréductibles. Des résultats positifs et négatifs sont obtenus sous plusieurs contraintes concernant la largeur, l’acyclicité, et la taille des prémisses dans la base d’implication. Les deux parties de la thèse sont parsemées d’énumération des transversaux minimaux d’un hypergraphe, et de notions liées
This thesis focuses on graphs, hypergraphs, and lattices. We study the complexity of the dualization of monotone Boolean functions, and its generalizations, through the many shapes it takes on these structures: minimal dominating sets enumeration, minimal transversals enumeration, lattice dualization, and meet-irreducible enumeration. Both tractable and intractable results are obtained, and future research directions are proposed. The thesis is organized as follows. A first part is devoted to the enumeration of minimal dominating sets in graphs. We obtain new output-polynomial time algorithms in graph classes related to Kt-free graphs and to posets of bounded dimension. A second part is devoted to generalizations of this problem in lattices. One generalization concerns the dualization in lattices given by implicational bases, the other deals with the enumeration of meet-irreducible elements. Both tractability and intractability results are obtained under various restrictions concerning width, acyclicity, and premises’ size in the implicational base. The two parts are sprinkled with hypergraph transversals enumeration and related notions

Cette thèse étudie certaines inégalités isopérimétriques globales sur les graphes métriques et les variétés riemanniennes. Tout d'abord, nous établissons pour un graphe métrique une inégalité isopérimétrique entre l'entropie volumique et la systole, puis étudions la géométrie de la boule unité de la norme stable en fonction de la combinatoire du graphe. Nous poursuivons en montrant que, pour une variété riemannienne fermée (M,g) de dimension au moins trois et de premier nombre de Betti non nul, une large classe de polytopes apparaît comme boule unité de la norme stable d'une métrique dans la classe conforme de g. Nous exhibons ensuite une borne supérieure de la constante systolique de la somme connexe de n exemplaires d'une variété M, montrant ainsi que la croissance de la constante systolique en fonction de n est toujours plus lente que la croissance linéaire. Enfin, nous démontrons une inégalité entre la systole, la longueur du lacet systolique et le diamètre d'une variété riemannienne simplement connexe dont le second groupe homotopique est non trivial.

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints
Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs

Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés

A (convex) polytope P is said to be 2-level if every hyperplane H that is facet-defining for P has a parallel hyperplane H' that contains all the vertices of P which are not contained in H.Two level polytopes appear in different areas of mathematics, in particular in contexts related to discrete geometry and optimization. We study the problem of enumerating all combinatorial types of 2-level polytopes of a fixed dimension d. We describe the first algorithm to achieve this. We ran it to produce the complete database for d <= 8. Our results show that the number of combinatorial types of 2-level d-polytopes is surprisingly small for low dimensions d.We provide an upper bound for the number of combinatorially inequivalent 2-level d-polytopes. We phrase this counting problem in terms of counting some objects called 2-level configurations, that capture the class of "maximal" rank d 0/1-matrices, including (maximal) slack matrices of 2-level cones and 2-level polytopes. We provide a proof that the number of d-dimensional 2-level configurations coming from cones and polytopes, up to linear equivalence, is at most 2^{O(d^2 log d)}.Finally, we prove that the extension complexity of every stable set polytope of a bipartite graph with n nodes is O(n^2 log n) and that there exists an infinite class of bipartite graphs such that, for every n-node graph in this class, its stable set polytope has extension complexity equal to Omega(n log n).
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis.   The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs.     In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA.

SANTOS, M. C. Experimentos Computacionais com Implementações de Conjunto por Endereçamento Direto e o Problema de Conjunto Independente Máximo. 2013. 78 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013.
Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T19:19:39Z No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5)
Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:28:47Z (GMT) No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5)
Made available in DSpace on 2015-09-23T16:28:47Z (GMT). No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) Previous issue date: 2013
The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs.
A utilização de vetores de bits é prática corrente na representação de conjuntos por endereçamento direto com o intuito de reduzir o espaço de memória necessário e melhorar o desempenho de aplicações com uso de técnicas de paralelismo em bits. Nesta dissertação, examinamos implementações para representação de conjuntos por endereçamento direto. A estrutura básica nessas implementações é o vetor de bits. No entanto, além dessa estrutura básica, implementamos também duas variações. A primeira delas consiste em uma estratificação de vetores de bits, enquanto a segunda emprega uma tabela de dispersão. As operações associadas às estruturas implementadas são a inclusão ou remoção de um elemento do conjunto e a união ou interseção de dois conjuntos. Especial atenção é dada ao uso de paralelismo em bits nessas operações. As implementações das diferentes estruturas nesta dissertação utilizam uma interface e uma implementação abstrata comuns, nas quais as operações são especificadas e o paralelismo em bits é explorado. A diferença entre as implementações está apenas na estrutura utilizada. Uma comparação experimental é realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente máximo. Duas abordagens são utilizadas na implementação de algoritmos enumerativos para o problema de conjunto independente máximo, ambas explorando o potencial de paralelismo em bits na representação do grafo e na operação sobre subconjuntos de vértices. A primeira delas é um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o método das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiência quando empregado no cálculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais são apresentados como forma de comparação entre os dois algoritmos e como forma de avaliação das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no método das bonecas russas é mais eficiente quanto ao tempo de execução e quanto ao consumo de memória. Além disso, os resultados experimentais mostram também que o uso de estratificação e tabelas de dispersão permitem ainda maior eficiência no caso de grafos com muito vértices e poucas arestas.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior
A utilizaÃÃo de vetores de bits à prÃtica corrente na representaÃÃo de conjuntos por endereÃamento direto com o intuito de reduzir o espaÃo de memÃria necessÃrio e melhorar o desempenho de aplicaÃÃes com uso de tÃcnicas de paralelismo em bits. Nesta dissertaÃÃo, examinamos implementaÃÃes para representaÃÃo de conjuntos por endereÃamento direto. A estrutura bÃsica nessas implementaÃÃes à o vetor de bits. No entanto, alÃm dessa estrutura bÃsica, implementamos tambÃm duas variaÃÃes. A primeira delas consiste em uma estratificaÃÃo de vetores de bits, enquanto a segunda emprega uma tabela de dispersÃo. As operaÃÃes associadas Ãs estruturas implementadas sÃo a inclusÃo ou remoÃÃo de um elemento do conjunto e a uniÃo ou interseÃÃo de dois conjuntos. Especial atenÃÃo à dada ao uso de paralelismo em bits nessas operaÃÃes. As implementaÃÃes das diferentes estruturas nesta dissertaÃÃo utilizam uma interface e uma implementaÃÃo abstrata comuns, nas quais as operaÃÃes sÃo especificadas e o paralelismo em bits à explorado. A diferenÃa entre as implementaÃÃes està apenas na estrutura utilizada. Uma comparaÃÃo experimental à realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente mÃximo. Duas abordagens sÃo utilizadas na implementaÃÃo de algoritmos enumerativos para o problema de conjunto independente mÃximo, ambas explorando o potencial de paralelismo em bits na representaÃÃo do grafo e na operaÃÃo sobre subconjuntos de vÃrtices. A primeira delas à um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o mÃtodo das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiÃncia quando empregado no cÃlculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais sÃo apresentados como forma de comparaÃÃo entre os dois algoritmos e como forma de avaliaÃÃo das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no mÃtodo das bonecas russas à mais eficiente quanto ao tempo de execuÃÃo e quanto ao consumo de memÃria. AlÃm disso, os resultados experimentais mostram tambÃm que o uso de estratificaÃÃo e tabelas de dispersÃo permitem ainda maior eficiÃncia no caso de grafos com muito vÃrtices e poucas arestas.
The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs.

Introducció Les deformitats angulars de les extremitats inferiors són molt freqüents en els nens i en ocasions poden necessitar d'una correcció quirúrgica. En l'actualitat l'hemiepifisiodesi temporal és el tractament més utilitzat per corregir les deformitats angulars en el nen en creixement. L'hemiepifisiodesi basa la seva capacitat de correcció en guiar el creixement de l'os mitjançant la frenada asimètrica de la placa fisaria. Tradicionalment, des de la descripció de la tècnica per Blount, l'hemiepifisiodesi s'havia realitzat amb grapes amb bons resultats en la correcció, però la tècnica no estava lliure de certes complicacions que en ocasions comprometien el resultat. En l'última dècada, com a resposta als problemes relacionats amb les grapes han aparegut nous sistemes d'hemipifisiodesi temporal, el més conegut d'ells és l'anomenada placa en vuit. Objectius L'objectiu d'aquesta tesi és valorar si existeixen diferències significatives entre els dos sistemes d'hemiepifisiodesi més utilitzats: la grapa i la placa en vuit, tant en el grau de deformitat que poden crear com en la velocitat d'aparició de la deformitat. Addicionalment, observar si els dos sistemes són igual de segurs. Material i mètodes Aquest és un estudi experimental prospectiu, randomitzat, on es van utilitzar conills Nova Zelanda de 8 setmanes. Es van establir tres grans grups: grapes, controls i plaques en vuit amb diferents subgrups segons el nombre de grapes col•locat o la longitud dels cargols utilitzats en la placa en vuit. En el disseny experimental es van estudiar les variables relacionades amb la capacitat de crear/corregir deformitat de cadascú dels dos sistemes i els efectes que provocaven sobre l'estructura de la fisi. Altres variables estudiades per comprendre les diferències trobades, van ser els efectes de la influència del nombre de punts de bloqueig de la fisi sobre la capacitat de crear deformitat i, específicament dins del model de la placa en vuit, els efectes que pugui tenir la longitud del cargol sobre el grau i intensitat de deformitat generat. La deformitat en varo produïda pels implants es va quantificar mitjançant el mesurament de l'angle epifiso-diafisari en radiografies seriades setmanals de les tibies. Els animals van ser sacrificats a diferents intervals setmanals des de la col•locació dels implants, es van obtenir i es van processar les tíbies per al seu estudi histològic. Els paràmetres histològics estudiats van incloure: l'alçària de la placa de creixement, la cel•lularitat, i la morfologia de la placa de creixement. Resultats i conclusions Les troballes histològiques suggereixen que tant la placa en vuit com les grapes produeixen forces de compressió sobre la placa de creixement, però la placa en vuit ho fa de forma més gradual. Els resultats dels estudis radiològics suggereixen que la hemiepifisiodesi amb dues grapes és més ràpida en produir deformitat inicialment, però eventualment la placa en vuit acaba sent més efectiva provocant deformitat. Però si es compara amb una sola grapa, aquesta és igual d'efectiva que la placa en vuit en produir deformitat, suggerint que el nombre de punts de bloqueig de la fisi pot jugar un paper en el grau i intensitat de la deformitat produïda. Els estudis radiològics comparatius utilitzant diferents longituds de cargols a la placa en vuit mostren que les diferents longituds no varien la capacitat de crear deformitat de l'implant, però histològicament l'ús de cargols llargs provoca major alteració histològica de la placa de creixement que amb l'ús dels cargols curts.
Introducción Las deformidades angulares de las extremidades inferiores son muy frecuentes en los niños y en ocasiones pueden precisar de una corrección quirúrgica. En la actualidad, la hemiepifisiodesis temporal es el método quirúrgico más utilizado para su tratamiento. La hemiepifisiodesis basa su capacidad de corrección en guiar el crecimiento del hueso mediante el frenado asimétrico del crecimiento de la placa fisaria. Tradicionalmente, desde la descripción de la técnica por Blount, la hemiepifisiodesis se había realizado con grapas con buenos resultados en general, pero la técnica no estaba exenta de complicaciones que en ocasiones comprometían el resultado. En la última década, como respuesta a los problemas relacionados con las grapas han aparecido nuevos sistemas de hemiepifisiodesis temporal, el más conocido de ellos es la denominada placa en ocho. Objetivos El objetivo de esta tesis es valorar si existen diferencias significativas entre los dos sistemas de hemiepifisiodesis más utilizados: la grapa y la placa en ocho, tanto en el grado de deformidad que son capaces de generar como en la velocidad de aparición. Adicionalmente observar si ambos sistemas son igualmente seguros. Material y métodos Éste es un estudio experimental prospectivo, randomizado, donde se utilizaron conejos Nueva Zelanda de 8 semanas. Se establecieron tres grandes grupos: grapas, controles y placas en ocho con diferentes subgrupos según el número de grapas colocado o la longitud de los tornillos utilizados en la placa en ocho. En el diseño experimental se estudiaron las variables relacionadas con la capacidad de crear/corregir deformidad de cada uno de los dos sistemas y los efectos que provocaban sobre la estructura de la fisis. Otras variables adicionales estudiadas para comprender las diferencias encontradas, fueron los efectos de la influencia del número de puntos de bloqueo de la fisis sobre la capacidad de crear deformidad y, específicamente dentro del modelo de la placa en ocho, los efectos que pudiera tener la longitud del tornillo sobre el grado e intensidad de deformidad generado. La deformidad en varo producida por los implantes se cuantificó mediante medición del ángulo epifiso-diafisario en radiografías seriadas semanales de las tibias. Los animales fueron sacrificados a diferentes intervalos de tiempo desde la colocación de los implantes, y se procesaron las tibias para su estudio histológico. Los parámetros histológicos estudiados incluyeron: la altura de la placa de crecimiento, la celularidad, y la morfología de la placa de crecimiento. Resultados y conclusiones. Los hallazgos histológicos sugieren que tanto la placa en ocho como las grapas producen fuerzas de compresión sobre la placa de crecimiento, pero la placa en ocho lo hace de forma más gradual. Los resultados de los estudios radiológicos sugieren que la hemiepifisiodesis con dos grapas es más rápida en producir deformidad inicialmente, pero la placa en ocho acaba siendo, finalmente, más efectiva en provocar deformidad. Sin embargo, si se comparan con una sola grapa, ésta es igual de efectiva que la placa en ocho en producir deformidad, lo que sugiere que el número de puntos de bloqueo de la fisis puede jugar un rol importante en el grado e intensidad de la deformidad producida. Los estudios radiológicos comparativos utilizando diferentes longitud de tornillos en la placa en ocho muestran que las variaciones en longitud no alteran la capacidad de crear deformidad del implante, aunque, histológicamente el uso de tornillos largos resulta en una mayor alteración histológica de la placa de crecimiento que con el uso de los tornillos cortos.
Introduction The angular deformities of the lower limb are common in children and eventually may need surgical treatment. Temporary hemiepiphysiodesis is the most common method used for treatment. Correction by this method is based on guided growth by asymmetrical temporary physeal growth arrest. Classically, the Blount staples have been used for treatment with very acceptable results, but occasionally complications may appear compromising success. To try to overcome these complications new implants have surged during the last decade, the best known is the 8-plate. Objectives The goal of this study was to elucidate if significant differences existed between the two hemiepiphysidesis devices: the staples and the 8-plate, by assessing the intensity and velocity of deformity production of both systems. In the event that differences existed, we would search for the factors that could explain such variations as well as to assess and compare the complication rate of these devices. Material and methods This is a prospective, randomized, experimental study using 8-weeks old New Zealand rabbits. Three groups were established: staples, controls and eight plates. Different subgroups were added according to the number of staples placed and on the length of the screws used in the 8-plate construct. Variables related to the ability to create deformity and the effects over the growth plate structure, were used in the study design. Besides, the effect of the growth plate tethering at one or more points was studied to understand the differences encountered between systems. Additionally the variable of screw length was studied for the 8-plate systems. The amount of varus deformity caused by the implants was quantified by means of the epiphyseal-diaphyseal angle measured in weekly tibia radiographs. Animals were sacrificed at different time intervals from the hemiepiphysiodesis and at sacrifice the tibias were harvested and histologically studied. The parameters analysed included: growth plate height, cellularity and morphology of the growth plate. Results and conclusions The histological findings suggest that both the 8-plate and staples produce compression on the growth plate; however, the 8-plate does it in a more gradual fashion. The radiological results show that the 2-staples hemiepiphysiodesis model produces deformity faster at early stages, but eventually, the 8-plate ends up being more effective in causing deformity. Nevertheless, when a single staple was used the results were identical to the 8-plate, which probably reflects that the area of physis tethered during hemiepiphysiodesis is more important than the device itself. As for the screw length, the radiological studies failed to demonstrate any effect in the amount of deformity created, despite the fact that the histological studies show that the short screws construct produced a lesser disturbance of the growth plate structure.

Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.

A maximum stable set is a stable set with the largest possible size, for a given graph G. This size is called the stability number of G, and it is denoted α(G). The problem of determining the stability number of an arbitrary graph, is a NP-complete optimization problem. As such, it is unlikely that there is a polynomial algorithm for finding a maximum stable set of a graph. The main purpose of this thesis is the achievement of recognition algorithms for graphs with convex quadratic stability number that are graphs whose stability number is equal to the optimal value of a convex quadratic program associated to the corresponding adjacency matrix . For that, results that relate the eigenvalues of the adjacency matrix and maximum stable sets are established and recognition algorithms are derived from those results. Such algorithms are applied to several well known problems such as efficient domination and the determination of graphs with perfect matchings and Hamiltonian cycles.
Um conjunto estável máximo num grafo G é um conjunto estável com cardinalidade máxima. A cardinalidade de um conjunto estável máximo chama-se número de estabilidade do grafo e denota-se α(G). O problema da determinação do número de estabilidade de um grafo arbitrário é um problema de optimização NP-completo e, como tal, não se conhecem algoritmos polinomiais capazes dessa determinação. O objectivo desta tese é a construção de algoritmos de reconhecimento para grafos com número de estabilidade quadrático convexo, que são grafos cujo número de estabilidade é igual ao valor óptimo de um programa quadrático convexo associado à respectiva matriz de adjacência. Com esse objectivo, apresentam-se resultados que relacionam os valores próprios da matriz de adjacência com a existência de estáveis máximos e descrevem-se algoritmos de reconhecimento baseados em tais resultados. Os algoritmos são posteriormente aplicados a vários problemas clássicos como o da dominação eficiente e da existência de emparelhamentos perfeitos e de ciclos de Hamilton.
Programa Doutoral em Matemática

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.