Dans cette thèse, nous étudions des problèmes de transversaux d'un point de vue tant algorithmique que combinatoire. Etant donné un hypergraphe, un transversal est un ensemble de sommets qui touche toutes les hyperarêtes. Un packing est un ensemble d'hyperarêtes deux à deux disjointes. Alors que la taille minimale d'un transversal est au moins égale à la taille maximale d'un packing on ne peut pas dans le cas général borner la taille minimale d'un transversal par une fonction du packing maximal. Dans un premier temps, un état de l'art rappelle les différentes conditions qui assurent l'existence de bornes supérieures sur la taille des transversaux, en particulier en fonction de la taille d'un packing. La plupart d'entre elles sont valables lorsque la VC-dimension de Vapnik-Chervonenkis de l'hypergraphe, est bornée. L'originalité de la thèse consiste à utiliser ces outils d'hypergraphes pour obtenir des résultats sur des problèmes de graphes. Nous prouvons notamment une conjecture de coloration de Scott dans le cas des graphes sans-triangle maximaux; ensuite, nous généralisons un résultat de Chepoi, Estellon et Vaxès traitant de domination à grande distance; enfin nous nous attaquons à une conjecture de Yannakakis sur la séparation des cliques et des stables d'un graphe.Dans un second temps, nous étudions les transversaux d'un point de vue algorithmique. On se concentre plus particulièrement sur les problèmes de séparation de graphe où on cherche des transversaux à un ensemble de chemin. En combinant des outils de connexité, les séparateurs importants et le théorème de Dilworth, nous obtenons un algorithme FPT pour le problème Multicut paramétré par la taille de la solution. / In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.

Orientador: Maria Lucia Pereira Antunes / Banca: Antonio Carlos Vieira Coelho / Banca: Fabiano Tomazini da Conceição / Resumo: A indústria têxtil é responsável pela geração de efluentes que, normalmente, apresentam um nível indesejável de coloração devido à etapa de tingimento, onde utilizam-se corantes que, quando lançados nos corpos d'água, levam à alteração de sua qualidade e ocasionam efeitos danosos ao meio ambiente e à saúde humana. Em vista disso, este trabalho teve como objetivo utilizar a lama vermelha, resíduo gerado em larga escala na produção de alumínio, como meio adsorvedor do corante Reativo Blue 19, o qual possui grande aplicação industrial e características que dificultam sua remoção em solução aquosa por meio de tratamentos convencionais. Sendo assim, optou-se por ativar a lama vermelha através de tratamento químico (água do mar, nitrato de cálcio e peróxido de hidrogênio) e térmico (400ºC e 500ºC), visando identificar a interferência desses tratamentos no aumento de sua capacidade adsortiva. Para isso, foi realizada a caracterização das amostras de lama vermelha através da determinação do pH, condutividade elétrica, ponto de carga zero (PCZ) difração de raios - x (DRX) e área superficial específica, sendo que a análise granulométrica foi realizada somente para a lama vermelha "in natura". Em seguida, visando determinar a capacidade adsortiva da lama vermelha ativada, foram construídas isortermas de adsorção, linearizadas segundo os modelos de Langmuir e Freundlich. Para efeito de comparação, a mesma metodologia foi aplicada ao carvão ativado visando determinar sua capacidade em adsorver o mesmo corante. Foi realizado o estudo da cinética de reação através dos modelos pseudo-segunda ordem, onde todas as amostras obedeceram ao modelo de pseudo - segunda ordem. Os resultados mostraram-se bastante promissores, sendo que a lama vermelha ativada por nitrato de cálcio a 500ºC apresentou uma... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The textile industry is responsible for the generation of effluents usually have an undersirable level of staining due to the step of dyeing, which is used dye which, when thrown into water bodies, leading to alteration of its quality and cause harmful effects the environment and human health. As a result, this study aimed to use the red mud, waste generated on a large scale in the production of aluminum, such as through adsorption of the dye Reactive Blue 19, which has a large industrial application and characteristics that hinder its removal in solution Aqueous by conventional treatments. Therefore, we chose to activate the red mud by chemical treatment (seawater, calcium nitrate and hydrogen peroxide) and thermal (400º C and 500º C) in order to identify the influence of these treatment in increasing its adsorption capacity. For this, we performed the characterization of samples of samples of red mud by determining the pH, electrical conductivity, point of zero charge (PZC) - ray diffraction (XRD) and specific surface area, and the particle size analysis was performed only for red mud "in nature". Then, to determine the adsorptive capacity of activated red mud, adsorption isotherms were constructed, according to the linearized Langmuir and Freundlich models. For comparison, the same methodology was applied to activated carbon in order to determine their ability to adsorb the same dye. Was performed to study the kinetics of reaction through the pseudo-first model and pseudo-second order where all samples followed the type of pseudo-second order. The results were very promising, with the red mud activated by calcium nitrate at 500ºC showed a maximum adsorption capacity of 476.02 mg/g at pH 4. The results for the activated carbon did not indicate affinity between the adsorbate and adsorbate material, a factor... (Complete abstract click electronic access below) / Mestre

Orientador: Maria do Socorro Nogueira Rangel / Banca: Samuel Jurkiewicz / Banca: Cleonice Fátima Bracciali / Resumo: O objetivo desse trabalho é apresentar o problema de coloração em grafos sob diferentes perspectivas. Caracterizamos o polinômio cromático de um grafo e enunciamos algumas de suas propriedades. Apresentamos duas formulações matemáticas para o problema de coloração de vértices e um método de solução para cada formulação. Apresentamos e discutimos propostas de atividades para o desenvolvimento de uma Oficina de Coloração para alunos do Ensino Médio e Fundamental. / Abstract: In this work the graph coloring problem was presented under di erent perspectives. We define the chromatic polynomials of a graph and describe some of its properties. Furthermore, two solution methods for the vertex coloring problem, through integer programming formulation, has been presented. We propose and discuss some activities for the development of a Workshop for students of secondary school. / Mestre

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / O problema de coloraÃÃo de vÃrtices à considerado um dos modelos mais estudados em teoria dos grafos pela sua relevÃncia em campos prÃticos e teÃricos. Do ponto de vista teÃrico, o problema de coloraÃÃo à NP - DifÃcil. AlÃm disto, foi classificado entre os problemas mais difÃceis de NP, no sentido de que achar uma aproximaÃÃo para o nÃmero cromÃtico tambÃm à NP - DifÃcil. A importÃncia do problema de coloraÃÃo tem incentivado a investigar mÃtodos para encontrar limitantes inferiores prÃximos do nÃmero cromÃtico. Historicamente, os primeiros limitantes inferiores utilizados para resolvÃ-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilizaÃÃo de relaxaÃÃes lineares de formulaÃÃes de programaÃÃo inteira. Uma formulaÃÃo que mostrou bons limitantes inferiores foi a formulaÃÃo por conjuntos independentes, cujo valor de relaxaÃÃo equivale ao nÃmero cromÃtico fracionÃrio. No presente trabalho, fazemos uma comparaÃÃo entre as formulaÃÃes de programaÃÃo inteira conhecidas para indicar a escolha pela formulaÃÃo dos representantes. Revisamos a formulaÃÃo para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluÃÃes inteiras. Discutimos como à possÃvel utilizar a formulaÃÃo dos representantes para gerar limites inferiores para o nÃmero cromÃtico fracionÃrio. Realizamos a implementaÃÃo de um mÃtodo de planos de corte para aproximar o nÃmero cromÃtico fracionÃrio e mostramos que podemos gerar limitantes inferiores que normalmente nÃo diferem em mais de uma unidade. / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value.

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-06-18T15:59:03Z No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-18T18:57:13Z (GMT) No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-18T18:58:47Z (GMT) No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) / Made available in DSpace on 2015-06-18T18:58:47Z (GMT). No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) Previous issue date: 2014-03-20 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The channel allocation problem is addressed, where, as a wireless mobile network with transmission antennas distributed in the region of interest and one or more given track limited frequency discretized broadcast channels, is to promote allocation of such channels by the antennas in such a way to meet the demand for calls optimizing the use of resources, which in this case prioritized to optimize the use of channels allocated in an optimization problem Min-Max distribution channel - the Span -, where the highest allocated channel must be as small as possible. This problem has a increasingly important given the large demand growth and limiting technological resources of communication involved. The approach to the problem is Optimization Combinatorics and related fields. Therefore, a literature study is presented on the topic, focusing on mobile phones and networks based on cognitive radio networks. The From this, it is proposed new theoretical model for the problem representation using special stains on graphs, task scheduling on parallel machines resource constraints and geometry distances with constraint programming, and possible to identify specific characteristics of some application scenarios of the problem general. Based on these models, the developed algorithms are presented and implemented, and approximate methods based on local search with emphasis on meta-heuristic simulated annealing, and exact methods, involving branch-and-cut with IBM / ILOG CPLEX tool and, finally, hybrid methods, prune-branch-and-bound. The computational experiments are presented with a comparative analysis of performance, either using classical literature instances, as set Philadelphia and its variants as well as artificial instances proposals to cover variants discussed, as well as larger involving network 70 to to 150 stations. The results validate the proposed theoretical models and algorithms developed and implemented, since, equal or better results to the literature were obtained with several great solutions proven, beyond theoretical discussion and variants proposals believed to strengthen the understanding of the problem and the related literature / O problema de alocação de canais é abordado, onde, dado uma rede móvel sem fio com antenas de transmissão distribuídas na região de interesse e dada uma ou mais faixa de frequência limitada discretizada em canais de transmissão, consiste em promover uma alocação de tais canais pelas antenas de tal modo a atender as chamadas em demanda otimizando o uso dos recursos, que neste caso priorizou-se a otimização do uso dos canais alocados, em um problema de otimização Min-Max da distribuição dos canais - o span -, onde o maior canal alocado deve ser o menor possível. Tal problema possui uma importância cada vez maior dado o grande crescimento da demanda e a limitação dos recursos tecnológicos de comunicação envolvidos. A abordagem ao problema é de Otimização Combinatória e áreas afins. Sendo assim, é apresentado um estudo da literatura sobre o tema, com enfoque em redes celulares e redes baseadas em rádios cognitivos. A partir disto, propõe-se novos modelos teóricos para representação do problema utilizando colorações especiais em grafos, escalonamento de tarefas em máquinas paralelas com restrições de recursos e geometria de distâncias com programação por restrições, sendo possível identificar características específicas de alguns cenários de aplicação do problema geral. Com base em tais modelos, são apresentados os algoritmos desenvolvidos e implementados, sendo métodos aproximados, baseados em busca local com ênfase na meta-heurística simulated annealing, e métodos exatos, envolvendo branch-and-cut com a ferramenta IBM/ILOG CPLEX e, por fim, métodos híbridos, branch-prune-and-bound. Os experimentos computacionais realizados são apresentados com uma análise comparativa de desempenho, usando tanto instâncias clássicas da literatura, como o conjunto Philadelphia e suas variantes, como também instâncias artificiais propostas para contemplar variantes abordadas, bem como de maior tamanho, envolvendo redes entre 70 a 150 estações. Os resultados obtidos validam os modelos teóricos propostos e os algoritmos desenvolvidos e implementados, uma vez que, resultados iguais ou melhores aos da literatura foram obtidos, com várias soluções ótimas comprovadas,além da discussão teórica e variantes propostas que se acredita robustecer o entendimento do problema e a literatura relacionada.

Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration. / In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems.

In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.

The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.

Despite the benefit of the memory hierarchy, it is still essential, in order to reduce accesses to higher levels of memory, to have an efficient usage of registers and local memories (also called scratchpad memories) present in most embedded processors, graphical processors (GPUs) and network processors. During the compilation, from a source language to an executable code, there are two optimizations that are of utmost importance: the register allocation and the local memory allocation. In this thesis's report we are interested in decoupled approaches, solving separately the allocation and assignment problems, that helps to improve the quality of the register and local memory allocations. In the first part of this thesis we are interested in two aspects of the register allocation problem: the improvements of the just-in-time (JIT) register allocation and the spill minimization problem. We introduce the split register allocation which leverages the decoupled approach to improve register allocation in the context of JIT compilation. We experimentally validate the effectiveness of split register allocation and its portability with respect to register count variations, relying on annotations whose impact on the bytecode size is negligible. We introduce a new decoupled approach, called iterated-optimal allocation, which focus on the spill minimization problem. The iterated-optimal allocation algorithm achieves results close to optimal while offering pseudo-polynomial guarantees for SSA programs and fast allocations on general programs. In the second part of this thesis, we study how a decoupled local memory allocation can be proposed in light of recent progresses in register allocation. We first validate our intuition for decoupled approach to local memory allocation. Then, we study the local memory allocation in a more theoretical way setting the junction between local memory allocation for linearized programs and weighted interval graph coloring. We design and analyze a new variant of the ship-building problem called the submarine-building problem. We show that this problem is NP-complete on interval graphs, while it is solvable in linear time for proper interval graphs, equivalent to unit interval graphs. The submarine-building problem is the first problem that is known to be NP-complete on interval graphs, while it is solvable in linear time for unit interval graphs. In the third part of this thesis, we propose a heuristic-based solution, the clustering allocator, which decouples the local memory allocation problem and aims to minimize the allocation cost. The clustering allocator while devised for local memory allocation, it appears to be a very good solution to the register allocation problem. After many years of separation, this new algorithm seems to be a bridge to reconcile the local memory allocation and the register allocation problems.

In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.