Dans un graphe non orienté, le Problème de Coloration de Graphe (PCG) consiste à assigner à chaque sommet du graphe une couleur de telle sorte qu'aucune paire de sommets adjacents n'aient la même couleur et le nombre total de couleurs est minimisé. DSATUR est un algorithme exact efficace pour résoudre le PCG. Un de ses défauts est qu'une borne inférieure est calculée une seule fois au noeud racine de l'algorithme de branchement, et n'est jamais mise à jour. Notre nouvelle version de DSATUR surpasse l'état de l'art pour un ensemble d'instances aléatoires à haute densité, augmentant significativement la taille des instances résolues. Nous étudions trois formulations PLNE pour le Problème de la Somme Chromatique Minimale (PSCM). Chaque couleur est représentée par un entier naturel. Le PSCM cherche à minimiser la somme des cardinalités des sous-ensembles des sommets recevant la même couleur, pondérés par l'entier correspondant à la couleur, de telle sorte que toute paire de sommets adjacents reçoive des couleurs différentes. Nous nous concentrons sur l'étude d'une formulation étendue et proposons un algorithme de Branch-and-Price. / Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR is an effective exact algorithm for the VCP. We introduce new lower bounding techniques enabling the computing of a lower bound at each node of the branching scheme. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of solvable instances. Similar results can be achieved for a subset of high density DIMACS instances. We study three ILP formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. We focus on studying an extended formulation and devise a complete Branch-and-Price algorithm.

It is known to be an NP-complete problem to color a graph with a given number of colors. We present some approximation algorithms which come close to the desired number of colors. We also develop an algorithm that colors k-colorable graphs with ~O(n^a(k)) colors, where a(2)=0, a(3)=3/14 and a(k)=1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) for k >= 4, as presented in [20]. This formula has been generalized for new possible base algorithms. / Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zu färben, ist als NP-vollständig bekannt. Hier werden einige Algorithmen vorgestellt, die für dieses Problem eine gute Approximation liefern. Des Weiteren wird ein allgemeines Färbungsverfahren hergeleitet, das für k-färbbare Graphen den bisher besten existierenden Algorithmus darstellt. Es können k-färbbare Graphen mit ~O(n^a(k)) Farben gefärbt werden, wobei a(2)=0, a(3)=3/14 und a(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) für k >= 4 gilt [20]. Diese Formel wurde für neue Basisalgorithmen verallgemeinert.

Fluorescence-based imaging techniques provide a simple, highly sensitive method of studying live cells and whole organisms in real time. Without question, fluorophores such as GFP, fluorescein, and rhodamines have contributed vastly to our understanding of both cell biology and biochemistry. However, most of the fluorescent molecules currently utilized suffer from one major drawback, the use of visible light. Due to cellular autofluorescence and the absorbance of incident light by cellular components, fluorescence imaging with visible wavelength fluorophores often results in high background noise and thus a low signal-to-noise ratio. Fortunately, this situation can be ameliorated by altering the wavelength of light used during imaging. Near-infrared (NIR) light (650-900 nm) is poorly absorbed by cells; therefore, fluorophores excited by this light provide a high signal-to-noise ratio and low background in cellular systems. While these properties make NIR fluorophores ideal for cellular imaging, most currently available NIR molecules cannot be used in live cells. The first half of this thesis addresses the synthetic difficulties associated with preparing NIR fluorophores that can be used within living systems. Small molecule NIR fluorophores are inherently hydrophobic which makes them unsuitable for use in the aqueous environment of the cell. Water-solubility is imparted to these dyes through highly polar sulfonates, which subsequently prevents the dyes from entering the cell. The novel work presented here details vii synthetic routes to aid in the development of sulfonated NIR fluorophores, which can be delivered into live cells through the inclusion of an esterase-labile sulfonate protecting group. Application of these synthetic techniques should allow for the development of novel NIR fluorophores with intracellular applications. The second half of this thesis addresses the need for novel NIR imaging reagents. Although several classes of NIR scaffolds do exist, most NIR probes are derivatives of a single class, heptamethine indocyanines. The work described here increases this palette by displaying the ability of NIR oxazines to function as an imaging reagent in live cells and in vivo and as a molecular sensor of biologically-relevant environmental conditions. Combined, the work contained herein has the capacity to not only advance the current NIR toolkit, but to expand it so that fluorescence imaging can move out of the dark and into the NIR light.

Dans cette thèse, nous étudions des problématiques de graphes et de jeux combinatoires. Il existe de nombreux liens entre ces deux domaines : ainsi, les jeux sont un bon moyen de modéliser une opposition dans un problème d'optimisation, et dans l'autre sens plusieurs jeux classiques sont définis sur les graphes. Nous allons étudier deux problèmes de graphes et adapter des jeux combinatoires classiques pour y jouer sur des graphes. Dans un premier temps, nous étudions un problème de criticalité. Un graphe qui vérifie une certaine propriété, mais tel qu'une simple modification (ajout ou suppression d'arête ou de sommet) la lui fait perdre est appelé critique pour cette propriété. Nous nous intéressons au problème des graphes critiques pour la propriété ≪ avoir un diamètre égal à 2 ≫, appelés graphes D2C. La conjecture de Murty-Simon donne une borne supérieure sur le nombre d'arêtes d'un graphe D2C en fonction de son nombre de sommets. Or, des recherches récentes laissent supposer que cette borne peut être améliorée pour les graphes D2C non-bipartis. Nous démontrons donc une borne amoindrie pour une sous-famille de graphes D2C. Dans un deuxième temps, nous considérons un problème d'identification, laquelle consiste à assigner une étiquette à toutes les arêtes ou à tous les sommets d'un graphe, cette assignation devant engendrer une étiquette différente pour chaque sommet. Nous définissons une coloration d'arêtes par des ensembles d'entiers induisant une identification des sommets, et démontrons que cette coloration nécessite au plus un nombre logarithmique d'entiers par rapport à l'ordre du graphe pour l'identifier. Ce résultat est mis en comparaison avec d'autres types de colorations identifiantes, qui nécessitent dans le pire des cas un nombre linéaire d'entiers pour identifier tous les sommets. Dans un troisième temps, nous étudions des jeux de suppression de sommets, qui sont des jeux dans lesquels deux joueurs suppriment d'un graphe des sommets en respectant certaines règles prédéfinies, le premier joueur incapable de jouer perdant la partie. Nous proposons un cadre global pour l'étude de nombreux jeux de suppression de sommets dans les graphes, qui inclut plusieurs jeux classiques comme Arc-Kayles et permet une généralisation des jeux de soustraction et des jeux octaux sur les graphes. Dans leur définition classique, ces jeux ont généralement des comportements réguliers : tous les jeux de soustraction finis sont ultimement périodiques et il est conjecture que c'est également le cas des jeux octaux. Nous étudions plus spécifiquement les jeux de soustraction connexes CSG(S), dans lesquels les joueurs peuvent supprimer k sommets induisant un sous-graphe connexe sans déconnecter le graphe si k ∈ S (avec S fini). Nous démontrons que tous ces jeux sont ultimement périodiques, dans le sens ou pour un graphe et un sommet donnés, un chemin attaché à ce sommet peut être réduit à partir d'un certain rang sans modifier la valeur de Grundy du graphe pour le jeu. Nous trouvons également des résultats de périodicité pure, en particulier sur les étoiles subdivisées : pour certains ensembles S, les chemins des étoiles peuvent être réduits à leur longueur modulo une certaine période sans changer l'issue du jeu. Enfin, nous définissons une variante pondérée de Arc-Kayles, appelée Weighted Arc-Kayles (ou WAK), dans laquelle les joueurs doivent sélectionner une arête pour réduire le poids de ses extrémités, les sommets ayant un poids nul étant supprimés du graphe. Nous montrons une réduction entre WAK et Arc-Kayles, puis que les valeurs de Grundy de WAK sont non-bornées, ce qui répond à une question ouverte sur Arc-Kayles. Nous montrons également que les valeurs de Grundy de WAK sont ultimement périodiques lorsque tous les poids du graphe sauf un sont fixes / In this thesis, we study both graphs and combinatorial games. There are several links betweenthose two domains : games are useful for modeling an opponent in optimization problems on graphs,and in the other direction several classical games are played on graphs. We will study two graphproblems and adapt some classical combinatorial games to be played on graphs.In a first chapter, we study a criticality problem. A graph that verifies some property, and suchthat any modification (vertex or edge addition or deletion) breaks the property is called critical forthis property. We focus on the critical graphs for the property "having diameter 2", called D2Cgraphs. The Murty-Simon conjecture gives an upper bound on the number of edges in a D2C graphwith a given number of vertices. However, recent research suggests that this bound can be improvedfor non-bipartite D2C graphs. We show the validity of this approach by proving a smaller upperbound for a subfamily of non-bipartite D2C graphs.In a second chapter, we consider an identification problem. Identification consists in assigningsome data to every edge or vertex of a graph, such that this assignment induces a label to everyvertex with the added condition that two distinct vertices must have a different label. We definean edge-coloring using sets of integers inducing an identification of the vertices, and prove that thiscoloring requires at most a logarithmic number of integers (with respect to the order of the graph)in order to successfully identify the vertices. This result is compared with other identifying colorings,for which the number of colors required to successfully identify the vertices can be linear with respectto the order of the graph.In order to show the link between graphs and games, we adapt a well-known family of games tobe played on graphs. We propose a general framework for the study of many vertex deletion games(which are games in which the players delete vertices from a graph under predefined rules) such asArc-Kayles. This framework is a generalization of subtraction and octal games on graphs. In theirclassical definition, those games exhibit a high regularity : all finite subtraction games are ultimatelyperiodic, and Guy conjectured that this is also true for all finite octal games.We specifically study the connected subtraction games CSG(S) (with S being a finite set). Inthose games, the players can remove k vertices from a graph if and only if they induce a connectedsubgraph, the graph remains connected after their deletion, and k ∈ S. We prove that those gamesare all ultimately periodic, in the sense that for a given graph and vertex, a path attached to thisvertex can be reduced (after a certain preperiod) without changing the Grundy value of the graph forthe game. We also prove pure periodicity results, mostly on subdivided stars : for some sets S, thepaths of a subdivided star can be reduced to their length modulo a certain period without changingthe outcome of the game.Finally, we define a weighted version of Arc-Kayles, called Weighted Arc-Kayles (WAKfor short). In this game, the players select an edge and reduce the weight of its endpoints. Verticeswith weight 0 are removed from the graph. We show a reduction between WAK and Arc-Kayles,then we prove that the Grundy values of WAK are unbounded, which answers an open question onArc-Kayles. We also prove that the Grundy values of WAK are ultimately periodic if we fix allbut one of the weights in the graph

Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis. / Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching.

O diagnóstico precoce dos Segundos Tumores Primários (STP) em pacientes já tratados por um carcinoma de cabeça e pescoço deve ser realizado, pois possibilita um tratamento resolutivo com baixa morbidade. O objetivo deste trabalho é avaliar se a cromoscopia com Lugol permite uma melhora na identificação de lesões malignas ou pré malignas em fases iniciais na boca e orofaringe, bem como se a imunoexpressão do p53 e da Metalotioneína no tumor índice predizem o aparecimento de um STP. Foi realizado um estudo prospectivo onde dois grupos comparáveis de portadores de carcinoma epidermóide de cabeça e pescoço foram formados (um com 106 pacientes e outro com 105 pacientes). Foram acompanhados durante um período médio de 25 meses aproximadamente. No primeiro grupo (grupo A) não foram utilizados corantes, já no segundo (grupo B) utilizou-se o Lugol. Foi observado um número de diagnósticos 200% maior no grupo em que foi utilizada a coloração de Lugol (grupo B) em relação ao grupo A. A imunoexpressão aumentada do p53 no tumor índice foi estatisticamente significante quando o paciente desenvolveu um segundo tumor primário diagnosticado pelo Lugol, não visível sem o corante, o que não ocorreu com a metalotioneína. / The early diagnosis of seconds primary tumors (STP) in patients already treated for carcinoma of the head and neck should be done, because enables a resolutive treatment with low morbidity. The objective of this paper is to evaluate whether chromoscopia using Lugols solution allows an improvement in the identification of malignant or pre malignant lesions in early stages in the mouth and oropharynx, and whether the expression of P53 and metallothionein in tumor index predict the emergence of a STP. A prospective study was conducted, where two groups statistically similar of patients with head and neck squamous cell carcinoma (one with 106 patients and another with 105 patients) were followed-up for a median period of 25 months, approximately. In the first group dyes were not used, and in the second Lugols solution was employed. It was observed a number of diagnoses 100%i higher in the group that Lugols solution was used. The increasing of P53 expression in tumor index was statistically significant when the patient developed a second primary tumor diagnosed by Lugol, not visible without dye, which has not occurred with metallothionein.

Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

Made available in DSpace on 2017-07-24T19:22:01Z (GMT). No. of bitstreams: 1 Rosana Marques Silva Figueroa.pdf: 3807885 bytes, checksum: 3650be97bf0d582c6f9fac01fcff5ea1 (MD5) Previous issue date: 2016-02-12 / Fundação Araucária de Apoio ao Desenvolvimento Científico e Tecnológico do Paraná / The aim of this study was to determine a microwave polymerization cycle that resulted in adequate physicomechanical and biological properties for the denture base acrylic resins polymerized in water bath (Vipi Cril-VC, VIPI®) or processed by microwave energy (Vipi Wave-VW, VIPI®). The evaluated polymerization cycles were: 1) WB (water bath) = (65ºC during 90 min + boiling during 90 min), recommended cycle for the VC resin; 2) M630/25 = 10 min at 270 W + 5 min at 0 W + 10 min at 360 W, recommended cycle for VW resin; 3) M650/5 = 5 min at 650 W; 4) M550/3 = 3 min at 550 W. The following properties were evaluated: degree of conversion (n=6), cytotoxicity (n=9), porosity (n=10), water sorption and solubility (n=10), and surface roughness and color stability (n=5) after immersion in potential colorant beverages and simulated toothbrushing. Data were submitted to analysis of variance ANOVA-2 way followed by Bonferroni’s test for degree of conversion and color stability, ANOVA-2 way for porosity and cytotoxicity, ANOVA-2 way followed by HSD Tukey’s test for water sorption and solubility, and ANOVA-3 way followed by Bonferroni’s test for surface roughness (α=0.05). For VC resin, there was no significant difference among the groups for degree of conversion. For VW resin, the lowest degree of conversion values appeared in the M630/25 and M650/5 cycles (P<0.05). Degree of conversion values ranged from 66.9 to 85.9%. There was no difference between the materials and experimental groups for cytotoxicity and all conditions resulted in non-cytotoxic effects. Porosity mean values below 1.52% with no significant difference among groups for both materials were observed. Resins showed water sorption and solubility values without a significant difference. The highest water sorption (2.43%) and solubility (0.13%) values were obtained for WB and M550/3, respectively (P<0.05). After immersion in coffee, M550/3 and WB groups of VC resin showed the highest and the lowest roughness values, respectively (P<0.05). There was also an increase in roughness of M550/3 group after immersion in wine (P<0.05). For VW resin, M650/5 group presented rougher surface after immersion in coffee (P<0.05). There was no difference in color among cycles for VW resin and VC resin showed more changes (P<0.05). All medium values were classified as acceptable, exception for VW resin (M630/25 group) which presented NBS=4.88 after immersion in wine. Vipi Cril conventional resin can be polymerized in microwave without impairment to the evaluated properties. According to the obtained results, the better experimental condition was the microwave polymerization at 650 W for 5 min for Vipi Cril. / O objetivo deste estudo foi determinar um ciclo de polimerização em micro-ondas que resultasse em propriedades físico-químicas e biológicas satisfatórias para resinas acrílicas termopolimerizáveis para base de prótese processadas em banho de água (Vipi Cril-VC, VIPI®) ou por energia de micro-ondas (Vipi Wave-VW, VIPI®). Os ciclos de polimerização avaliados foram: 1) BA (banho de água) = (65ºC por 90 min + 90 min em ebulição), ciclo recomendado para a resina VC; 2) M630/25 = 10 min a 270 W + 5 min a 0 W + 10 min a 360 W, ciclo recomendado para a resina VW; 3) M650/5 = 5 min a 650 W; 4) M550/3 = 3 min a 550 W. Foram avaliadas as seguintes propriedades: grau de conversão (n=6), citotoxicidade (n=9), porosidade (n=10), sorção de água e solubilidade (n=10) e rugosidade de superfície e estabilidade de cor (n=5) após imersão em líquidos potencialmente corantes e escovação simulada. Os resultados obtidos foram submetidos à análise de variância ANOVA-2 fatores seguida pelo teste de Bonferroni para grau de conversão e estabilidade de cor, ANOVA-2 fatores para porosidade e citotoxicidade, ANOVA-2 fatores seguida pelo teste de Tukey HSD para sorção de água e solubilidade e ANOVA-3 fatores seguida pelo teste de Bonferroni para rugosidade de superfície (α=0,05). Não houve diferença significante entre os grupos para os resultados de grau de conversão da resina VC. Para a resina VW, os valores mais baixos de grau de conversão foram obtidos nos ciclos M630/25 e M650/5 (P<0,05). Os valores médios de grau de conversão foram entre 66,9% e 85,9%. Não houve diferença entre os materiais e os grupos experimentais para os resultados de citotoxicidade e todas as condições resultaram em efeitos não citotóxicos. Foram observados valores médios de porosidade inferiores a 1,52%, sem diferença significante entre os grupos para ambos os materiais. As resinas apresentaram valores de sorção de água e solubilidade sem diferença estatisticamente significante entre elas. Os valores mais altos de sorção de água (2,43%) e de solubilidade (0,13%) foram obtidos nos grupos BA e M550/3, respectivamente (P<0,05). Com a imersão em café, os grupos M550/3 e BA da resina VC apresentaram os maiores e os menores valores de rugosidade de superfície, respectivamente (P<0,05). Também houve aumento da rugosidade do grupo M550/3 após imersão no vinho tinto (P<0,05). Para a resina VW, o grupo M650/5 demonstrou superfície mais rugosa após imersão em café (P<0,05). Não houve diferença de cor entre os ciclos para a resina VW e a resina VC apresentou mais alterações (P<0,05). Todos os valores médios de estabilidade de cor foram classificados como aceitáveis, exceto para a resina VW (grupo M630/25) que apresentou NBS=4,88 após imersão em vinho tinto. A resina Vipi Cril formulada para polimerização convencional pôde ser polimerizada em micro-ondas sem prejuízo às suas propriedades avaliadas. De acordo com os resultados obtidos, a melhor condição experimental foi a polimerização da resina Vipi Cril em micro-ondas a 650 W por 5 min.

O diagnóstico precoce dos Segundos Tumores Primários (STP) em pacientes já tratados por um carcinoma de cabeça e pescoço deve ser realizado, pois possibilita um tratamento resolutivo com baixa morbidade. O objetivo deste trabalho é avaliar se a cromoscopia com Lugol permite uma melhora na identificação de lesões malignas ou pré malignas em fases iniciais na boca e orofaringe, bem como se a imunoexpressão do p53 e da Metalotioneína no tumor índice predizem o aparecimento de um STP. Foi realizado um estudo prospectivo onde dois grupos comparáveis de portadores de carcinoma epidermóide de cabeça e pescoço foram formados (um com 106 pacientes e outro com 105 pacientes). Foram acompanhados durante um período médio de 25 meses aproximadamente. No primeiro grupo (grupo A) não foram utilizados corantes, já no segundo (grupo B) utilizou-se o Lugol. Foi observado um número de diagnósticos 200% maior no grupo em que foi utilizada a coloração de Lugol (grupo B) em relação ao grupo A. A imunoexpressão aumentada do p53 no tumor índice foi estatisticamente significante quando o paciente desenvolveu um segundo tumor primário diagnosticado pelo Lugol, não visível sem o corante, o que não ocorreu com a metalotioneína. / The early diagnosis of seconds primary tumors (STP) in patients already treated for carcinoma of the head and neck should be done, because enables a resolutive treatment with low morbidity. The objective of this paper is to evaluate whether chromoscopia using Lugols solution allows an improvement in the identification of malignant or pre malignant lesions in early stages in the mouth and oropharynx, and whether the expression of P53 and metallothionein in tumor index predict the emergence of a STP. A prospective study was conducted, where two groups statistically similar of patients with head and neck squamous cell carcinoma (one with 106 patients and another with 105 patients) were followed-up for a median period of 25 months, approximately. In the first group dyes were not used, and in the second Lugols solution was employed. It was observed a number of diagnoses 100%i higher in the group that Lugols solution was used. The increasing of P53 expression in tumor index was statistically significant when the patient developed a second primary tumor diagnosed by Lugol, not visible without dye, which has not occurred with metallothionein.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.