Necessary and sufficient conditions are given for the existence of isomorphic decompositions of the complete bipartite graph, the complete graph with a hole, and the λ-fold complete graph into copies of a 4-cycle with a pendant edge.

No description available.

Chordal graphs are an important class of perfect graphs. The beautiful theory surrounding their study varies from natural applications to elegant characterizations in terms of forbidden subgraphs, subtree representations, vertex orderings, and to linear time recognition algorithms. Haskins and Rose introduced the class of chordal digraphs as a digraph analogue of chordal graphs. Chordal digraphs can be defined in terms of vertex orderings and several results about chordal graphs can be extended to chordal digraphs. However, a forbidden subdigraph characterization of chordal digraphs is not known and finding such a characterization seems to be a difficult problem. Meister and Telle studied semi-complete chordal digraphs and gave a forbidden subdigraph characterization of this class of digraphs. In this thesis, we study chordal digraphs within the classes of quasi-transitive, extended semi-complete, and locally semi-complete digraphs. For each of these classes we obtain a forbidden subdigraph characterization of digraphs which are chordal. We also introduce in this thesis a new variant of chordal digraphs called semi-strict chordal digraphs. We obtain a forbidden subdigraph characterization of semi-strict chordal digraphs for each of the classes of semi-complete, quasi-transitive, extended semi-complete, and locally semi-complete digraphs. / Graduate

published_or_final_version / Dentistry / Doctoral / Doctor of Philosophy

The problem with which this paper is concerned is that of defining the Riemann-Complete Integral and comparing it with the Riemann and the Lebesgue Integrals.

Thesis advisor: Howard Straubing / The use of computer programs to automatically solve logic puzzles is examined in this work. A typical example of this type of logic puzzle is one in which there are five people, with five different occupations and five different color houses. The task is to use various clues to determine which occupation and which color belongs to each person. The clues to this type of puzzle often are statements such as, ''John is not the barber,'' or ''Joe lives in the blue house.'' These puzzles range widely in complexity with varying numbers of objects to identify and varying numbers of characteristics that need to be identified for each object. With respect to the theoretical aspects of solving these puzzles automatically, this work proves that the problem of determining, given a logic puzzle, whether or not that logic puzzle has a solution is NP-Complete. This implies, provided that P is not equal to NP, that, for large inputs, automated solvers for these puzzles will not be efficient in all cases. Having proved this, this work proceeds to seek methods that will work for solving these puzzles efficiently in most cases. To that end, each logic puzzle can be encoded as an instance of boolean satisfiability. Two possible encodings are proposed that both translate logic puzzles into boolean formulas in Conjunctive Normal Form. Using a selection of test puzzles, a group of boolean satisfiability solvers is used to solve these puzzles in both encodings. In most cases, these simple solvers are successful in producing solutions efficiently. / Thesis (BS) — Boston College, 2009. / Submitted to: Boston College. College of Arts and Sciences. / Discipline: College Honors Program. / Discipline: Computer Science.

by Chi-lok Chan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Scheduling Problems of Chain-like Task System --- p.4 / Chapter 2.1 --- Introduction --- p.4 / Chapter 2.2 --- Problem Assumptions and Notations Definition --- p.7 / Chapter 2.3 --- Related Works --- p.9 / Chapter 2.3.1 --- Bokhari's Algorithm --- p.10 / Chapter 2.3.2 --- Sheu and Chiang's Algorithm --- p.12 / Chapter 2.3.3 --- Hsu's Algorithm --- p.12 / Chapter 2.4 --- Decision Algorithms for Un-mergeable Task System --- p.18 / Chapter 2.4.1 --- Feasible Length-K Schedule --- p.18 / Chapter 2.4.2 --- Generalized Decision Test --- p.23 / Chapter 2.5 --- Dominated and Non-dominated Task Systems --- p.26 / Chapter 2.5.1 --- Algorithm for Dominated Task System --- p.26 / Chapter 2.5.2 --- Property of Non-dominated Task System --- p.27 / Chapter 2.6 --- A Searching-Based Algorithm for the Optimization Problem --- p.28 / Chapter 2.6.1 --- Algorithm --- p.29 / Chapter 2.6.2 --- Complexity Analysis --- p.31 / Chapter 2.7 --- A Searching Algorithm Based on a Sorted Matrix --- p.33 / Chapter 2.7.1 --- Sorted Matrix --- p.33 / Chapter 2.7.2 --- Algorithm for the Optimization Problem --- p.35 / Chapter 2.7.3 --- Complexity Analysis --- p.40 / Chapter 2.8 --- A Constructive Algorithm for the Optimization Problem --- p.43 / Chapter 2.9 --- A Modified Constructive Algorithm --- p.46 / Chapter 2.9.1 --- Algorithm --- p.46 / Chapter 2.9.2 --- Worst-Case Analysis --- p.50 / Chapter 2.9.3 --- Sufficient Condition for Efficient Algorithm H --- p.58 / Chapter 2.9.4 --- Average-Case Analysis --- p.62 / Chapter 2.10 --- Performance Evaluation --- p.65 / Chapter 2.10.1 --- Optimal Schedule --- p.65 / Chapter 2.10.2 --- Space Complexity Analysis --- p.67 / Chapter 2.10.3 --- Time Complexity Analysis --- p.68 / Chapter 2.10.4 --- Simulation of Algorithm F and Algorithm H --- p.70 / Chapter 2.11 --- Conclusion --- p.74 / Chapter 3 --- Vehicle Scheduling Problems with Time Window Constraints --- p.77 / Chapter 3.1 --- Introduction --- p.77 / Chapter 3.2 --- Problem Formulation and Notations --- p.79 / Chapter 3.3 --- NP-hardness of VSP-WINDOW-SLP --- p.83 / Chapter 3.3.1 --- A Transformation from PARTITION --- p.83 / Chapter 3.3.2 --- Intuitive Idea of the Reduction --- p.85 / Chapter 3.3.3 --- NP-completeness Proof --- p.87 / Chapter 3.4 --- Polynomial Time Algorithm for the VSP-WINDOW on a Straight Line with Common Ready Time --- p.98 / Chapter 3.5 --- Strong NP-hardness of VSP-WINDOW-TREEP --- p.106 / Chapter 3.5.1 --- A Transformation from 3-PARTITION --- p.107 / Chapter 3.5.2 --- NP-completeness Proof --- p.107 / Chapter 3.6 --- Conclusion --- p.111 / Chapter 4 --- Conclusion --- p.115 / Bibliography --- p.119

La génomique comparative est l'étude des relations structurales et fonctionnelles entre des génomes appartenant à différentes souches ou espèces. Cette discipline offre ainsi la possibilité d'étudier et de comprendre les processus qui façonnent les génomes au cours de l'évolution. Dans le cadre de cette thèse, nous nous sommes intéressés à la génomique comparative des bactéries et plus particulièrement aux méthodes relatives à la comparaison des séquences complètes d'ADN des génomes bactériens. Ces dix dernières années, le développement d'outils informatiques permettant de comparer des génomes entiers à l'échelle de l'ADN est devenu une thématique de recherche à part entière. Actuellement, il existe de nombreux outils dédiés à cette tâche. Cependant, jusqu'à présent, la plupart des efforts ont été dirigés vers la réduction du temps de calcul et l'optimisation de la mémoire au détriment de l'évaluation de la qualité des résultats obtenus. Pour combler ce vide, nous avons travaillé sur différents problèmes statistiques soulevés par la comparaison de génomes complets bactériens. Notre travail se divise en deux axes de recherche. Dans un premier temps, nous nous sommes employés à évaluer la robustesse des alignements de génomes complets bactériens. Nous avons proposé une méthode originale fondée sur l'application de perturbations aléatoires sur les génomes comparés. Trois scores différents sont alors calculés pour estimer la robustesse des alignements de génomes à différentes échelles, allant des nucléotides aux séquences entières des génomes. Notre méthode a été expérimentée sur des données génomiques bactériennes réelles. Nos scores permettent d'identifier à la fois les alignements robustes et non robustes. Ils peuvent être employés pour corriger un alignement ou encore pour comparer plusieurs alignements obtenus à partir de différents outils. Dans un second temps, nous avons étudié le problème de la paramétrisation des outils de comparaisons de génomes entiers. En effet, la plupart des outils existants manquent à la fois de documentation et de valeurs par défaut fiables pour initialiser leurs paramètres. Conséquemment, il y a un besoin crucial de méthodes spécifiques pour aider les utilisateurs à définir des valeurs appropriées pour les paramètres de ces outils. Une grande partie des outils de comparaisons de génomes complets est fondée sur la détection des matches (mots communs exacts). Le paramètre essentiel pour ces méthodes est la longueur des matches à considérer. Au cours de cette thèse, nous avons développé deux méthodes statistiques pour estimer une valeur optimale pour la taille des matches. Notre première approche utilise un modèle de mélange de lois géométriques pour caractériser la distribution de la taille des matches obtenus lorsque l'on compare deux séquences génomiques. La deuxième approche est fondée sur une approximation de Poisson de la loi du comptage des matches entre deux chaînes de Markov. Ces méthodes statistiques nous permettent d'identifier facilement une taille optimale de matches à la fois pour des séquences simulées et pour des données génomiques réelles. Nous avons également montré que cette taille optimale dépend des caractéristiques des génomes comparés telles que leur taille, leur composition en base ou leur divergence relative. Cette thèse représente une des toutes premières études dont l'objectif est d'évaluer et d'améliorer la qualité des comparaisons des génomes complets. L'intérêt et les limites de nos différentes approches sont discutés et plusieurs perspectives d'évolution sont proposées. / Comparative genomics is the study of the structural and functional relationships between genomes belonging to different strains or species. This discipline offers great opportunities to investigate and to understand the processes that shape genomes across the evolution. In this thesis, we focused on the comparative genomics of bacteria and more precisely, on methods dedicated to the comparison of the complete DNA sequences of bacterial genomes. This last decade, the design of specific computerized methods to compare complete genomes at the DNA scale has become a subject of first concern. Now, there exist many tools and methods dedicated to this task. However, until now, most of the efforts were directed to reduce execution time and memory usage at the expense of the evaluation of the quality of the results. To fill this gap, we worked on different statistical issues related to the comparison of complete bacterial genomes. Our work was conducted into two directions. In the first one, we investigated the assessment of the robustness of complete bacterial genome alignments. We proposed an original method based on random perturbations of the compared genomes. Three different scores were derived to estimate the robustness of genome alignments at different scales, from nucleotides to the complete genome sequences. Our method was trained on bacterial genomic data. Our scores allow us to identify robust and non robust genome alignments. They can be used to correct an alignment or to compare alignments performed with different tools. Secondly, we studied the problem of the parametrization of comparison tools. Briefly, most of the existing tools suffer from a lack of information and of reliable default values to set their parameters. Consequently, there is a crucial need of methods to help users to define reliable parameter values for these tools. Most of the comparison tools are rooted on the detection of word matches. The key parameter for all these tools is the length of the matches to be considered. During this thesis, we developed two statistical methods to estimate an optimal length for these matches. Our first approach consisted in using a mixture model of geometric distributions to characterize the distribution of the length of matches retrieved from the comparison of two genomic sequences. The second approach is rooted on a Poisson approximation of the number of matches between two Markov chains. These statistical methods allow us to easily identify an optimal length for the matches from both simulated and real genomic data. We also showed that this optimal length depends on the characteristics of the compared genomes such as their length, their nucleotide composition, and their relative divergence. This thesis represents one of the earliest attempts to statistically evaluate and to improve the quality of complete genome comparisons. The interest and limitations of our different methods are discussed and some perspectives are proposed.

Resumo: Este estudo teve por objetivo avaliar a efetividade da irradiação por microondas na esterilização de próteses totais. Para isso, oitenta próteses totais padronizadas foram confeccionadas e submetidas à esterilização com óxido de etileno. As próteses foram então individualmente inoculadas (107 ufc/mL) com meio de cultura de Tryptic Soy Broth (TSB) contendo um dos seguintes microrganismos: C.albicans, S. aureus, B. subtilis e P. aeruginosa. Após 48 horas de incubação a 37oC, 40 amostras foram imersas em 200 mL de água e irradiadas a 650 W por 6 minutos. Quarenta amostras não irradiadas foram utilizadas como controle. A seguir, 25 uL da suspensão resultante das diluições seriadas de 10-1 a 10-6, foram semeados em placas de Petri contendo os meios de cultura seletivos para cada microrganismo. Todas as placas foram incubadas a 37oC por 48 horas. Após a incubação, as colônias foram quantificadas em ufc/mL. Para verificação da efetividade exposição às microondas em longo prazo as amostras irradiadas foram imersas em meio de cultura e incubadas a 37oC por 7 dias. A esterilização foi obtida, após 48 horas, para as próteses contaminadas com C.albicans, S. aureus e B. subtilis. Um pequeno número de colônias foi observado em 2 placas de Petri para o microrganismo P. aeruginosa. Após 7 dias de incubação a 37oC houve crescimento microbiológico em 3 culturas de TSB, sendo 2 para P. aeruginosa e um para B. subtilis. Todas as próteses totais do grupo controle apresentaram crescimento microbiano nas placas de Petri, após 48 horas de incubação a 37oC. A irradiação por microondas por 6 minutos a 650 W provou ser um método rápido e efetivo para desinfecção das próteses totais contaminadas com P. aeruginosa e B. subtilis além, de promover a esterilização das inoculadas com C. albicans e S. aureus. / Abstract: The aim of this study was to evaluate the effectiveness of microwave irradiation on the sterilization of complete dentures contaminated with individual suspension of 3 bacterias (P. aeruginosa, S. aureus and B. subtilis) and one fungus (C. albicans). Eighty simulated maxillary complete dentures were fabricated in a standardized procedure and subjected to ethylene oxide sterilization. The dentures were individually inoculated (107 cfu/mL) with Tryptic Soy Broth (TSB) media containing one of the tested microorganisms. After incubation at 37°C for 48 hours, forty dentures were immersed in 200 mL of distilled water and submitted to microwave irradiation at 650 W for 6 minutes. Forty non - irradiated dentures were used as positive controls. Using 0.9% sodium chlorine solution as diluent, tenfold serial dilutions 10-1 - 10-6 were plated onto 4 selective media appropriate for each organism: Manitol Salt Agar for S. aureus, Miller Hinton for P. aeruginosa, Sabourand Agar containing 5 μg/mL gentamicin for C.albicans, and Tryptic Soy Agar for B. subtilis. All plates were incubated at 37°C for 48 hours and colonies counts of each plate were quantified (cfu/mL). To verify the long - term effectiveness ofmicrowave sterilization, the TSB beakers with the microwave specimens were incubated at 37°C for 7 days. Data were statistically analyzed by Kruskal - Wallis's test (α=0.05). Irradiated dentures showed consistent sterilization of S. aureus, B. subtilis and C. albicans after 48 hours. Compared to P. aeruginosa control, a very low number of colonies were detected only in two plates. Turbidity was observed in three broth beakers, two from P. aeruginosa and one from B. subtilis, after 7 days incubation at 37°C. All control dentures showed microbial...(Complete abstract, click electronic access below) / Orientador: Carlos Eduardo Vergani / Coorientador: Denise Madalena Palomari Spolidorio / Banca: Ana Cláudia Pavarina / Banca: Dalva Cruz Laganá / Mestre

Wong, Wing Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 66-67). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background Study --- p.4 / Chapter 2.1 --- Basic Definitions and Notations --- p.5 / Chapter 2.2 --- Tarjan and Trojanowski's algorithm --- p.6 / Chapter 2.2.1 --- Techniques --- p.6 / Chapter 2.2.2 --- Algorithm --- p.8 / Chapter 2.3 --- "Fomin, Grandoni and Kratsch's Algorithm" --- p.9 / Chapter 2.3.1 --- Techniques --- p.9 / Chapter 2.3.2 --- Algorithm --- p.14 / Chapter 3 --- Improvements --- p.18 / Chapter 3.1 --- Tarjan and Trojanowski´ةs Algorithm --- p.18 / Chapter 3.1.1 --- Correctness and Running Time Analysis --- p.28 / Chapter 3.1.2 --- Improvement --- p.30 / Chapter 3.1.3 --- Using more weights --- p.35 / Chapter 3.2 --- The First Algorithm --- p.37 / Chapter 3.2.1 --- Standard Analysis --- p.37 / Chapter 3.2.2 --- Measure and Conquer --- p.38 / Chapter 3.2.3 --- Using more weights --- p.42 / Chapter 3.3 --- The Second Algorithm --- p.43 / Chapter 3.3.1 --- Running Time Analysis --- p.44 / Chapter 3.3.2 --- Using More Weights --- p.45 / Chapter 3.4 --- The Third Algorithm --- p.46 / Chapter 4 --- Lower Bounds --- p.52 / Chapter 4.1 --- Tarjan and Trojanowski's Algorithm --- p.52 / Chapter 4.2 --- The First Algorithm --- p.55 / Chapter 4.3 --- The Second Algorithm --- p.58 / Chapter 4.4 --- The Third Algorithm --- p.60 / Chapter 5 --- Conclusion --- p.63 / Bibliography --- p.66