We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.

Η παρούσα διπλωματική έχει ως σκοπό να συνδέσει την λειτουργία υπάρχοντος ορθογράφου με συγκεκριμένη δομή αποθήκευσης και αναζήτησης λέξεων. Κριτήρια του ορθογράφου είναι να είναι ανοιχτού κώδικα και σκοπός είναι να του προστεθεί η δυνατότητα να λειτουργεί με ακυκλικούς γράφους, ντετερμινιστικούς ή μη. Τα πλεονεκτήματα της νέας δομής και λειτουργίας του ορθογράφου είναι πολλαπλά και παρουσιάζονται στη πορεία της διπλωματικής. Αν και οι δοκιμές που έγιναν, δεν αναδεικνύουν τα πλεονεκτήματα αυτά, σε θεωρητικό επίπεδο η εξέλιξη μπορεί να είναι μεγάλη, και σε ταχύτητα αλλά και σε απόδοση. / Target of this project is to connect the proccess of an existing speller to a spesific structure of storing and searching words. Basic criteria of this speller are: open source, capability to work with acyclic graphs, deteministic or not. The advantages of this new structure and proccess of the speller are presented in this project.

This thesis is concerned with the efficient computation of Jacobian matrices of nonlinear vector maps using automatic differentiation (AD). Specifically, we propose the use of two directed edge separator methods, the weighted minimum separator and natural order separator methods, to exploit the structure of the computational graph of the nonlinear system.This allows for the efficient determination of the Jacobian matrix using AD software. We will illustrate the promise of this approach with computational experiments.

To achieve economic development, regional authorities have to address issues that relate to climate change, efficient information flow in the market place, and health care. This dissertation presents three essays on current issues of concern to economic development in Africa. Climate change is examined in terms of its effects on the Egyptian agricultural sector; transmission of world price to small scale growers is examined in Uganda; and the benefits of insecticide-treated bed nets use is examined in Africa. In essay I, to address the impact of climate change on the Egyptian agricultural sector under alternative population growth rates, water use and crop yield assumption; the Egyptian Agricultural Sector Model (EASM) is updated and expanded to improve hydrological modeling and used to portray agricultural activity and hydrological flow. The results indicate that climate change will cause damages (costs) to the Egyptian agricultural sector and these will increase over time. Egypt may reduce these future damages by controlling its population growth rate and using water conservation strategies. In essay II, I use vector autoregressive analysis to examine the transmissions of price information to Uganda coffee growers; using monthly coffee price data on retail, futures, farmgate and world prices from 1994 to 2010. Improved transmission of world prices to farmers may increase their decision making to obtain a better market price. Directed acyclic graphs reveal that there is a causal flow of information from the indicator price to the London futures price to the Uganda grower?s price in contemporaneous time. Forecast error variance decomposition indicates that at moving ahead 12 months, the uncertainty in Uganda grower price is attributable to the indicator price (world spot price), own price (farmgate), London future and Spain retail price in rank order. In essay III, the cost of malaria in children under five years and the use of insecticide treated bed nets is examined in the context of 18 countries in Africa. I examine the direct and indirect cost of malaria in children under five years and the benefit of investing in insecticide treated mosquito nets as a preventative strategy in 18 African countries. The results indicate that the use of mosquito treated nets reduces the number of malaria cases in children; and this can induce 0.5% reduction in outpatient treatment costs, 11% reduction in inpatient treatment costs, 11% reduction in productivity loss, and 15% reduction in disability adjusted life years (DALY) annually.

Made available in DSpace on 2016-06-02T19:05:26Z (GMT). No. of bitstreams: 1 1631.pdf: 1988300 bytes, checksum: e305adb917a8fdf720897942982390b7 (MD5) Previous issue date: 2007-08-24 / Different algorithms provide efficient scheduling of parallel applications on distributed and heterogeneous computational platforms, such as computational grids. Most scheduling algorithms for such environments require an application model represented by a directed acyclic graph (DAG), selecting tasks for execution according to their processing and communication characteristics. The obtainment of DAGs for real applications, however, is not a simple quest. The required knowledge about the application tasks and the communication among them, considering existing transmission cycles, harden the elaboration of appropriate graphs. Particularly, MPI programs, that represent a meaningful portion of existing parallel applications, usually present a cyclic communication model among the master and the processing nodes. This behavior prevents most scheduling algorithms to be employed as they recursively traverse the graphs to prioritize the tasks. In this sense, this work presents a mechanism for the automatic creation of DAGs for real MPI application originally developed for homogeneous clusters. In order to do so, applications go through a monitored execution in a cluster and the collected data are used for the elaboration of an appropriate DAGs. Data dependencies are identified and existing cycles among the tasks are eliminated. The HEFT scheduling algorithm is used to evaluate the application model and the schedule obtained is then automatically converted into an RSL (Resource Specification Language) file for execution in a grid with Globus. Results from running real applications and simulations show using the grid can be advantageous. / Algoritmos diferentes possibilitam o escalonamento eficiente de aplicações paralelas em plataformas computacionais heterogêneas e distribuídas, tais como grids computacionais. Vários algoritmos de escalonamento para esses ambientes necessitam de um modelo de aplicação representado por um grafo acíclico direcionado (GAD), selecionando tarefas para execução de acordo com suas características de comunicação e de processamento. A obtenção de um GAD para uma aplicação real, contudo, não é uma questão simples. O conhecimento necessário sobre as tarefas da aplicação e as comunicações entre elas, considerando ciclos de transmissão, dificulta a elaboração de um grafo apropriado. Particularmente, programas MPI, os quais representam uma parcela significativa das aplicações paralelas, apresentam um modelo de comunicação cíclico entre o nó master e os nós de processamento. Esse comportamento impede a utilização de muitos algoritmos de escalonamento devido ao fato de eles percorrerem o grafo recursivamente para priorizar as tarefas. Nesse sentido, esse trabalho apresenta um mecanismo para a criação automática de GADs para aplicações MPI reais originalmente desenvolvidas para clusters homogêneos. Para essa implementação, aplicações são monitoradas durante a execução em um cluster e os dados coletados são usados para a elaboração de um GADs apropriados. Dependências de dados são identificadas e ciclos existentes entre as tarefas são eliminados. O algoritmo de escalonamento HEFT é usado para avaliar o modelo de aplicação e o escalonamento obtido é então automaticamente convertido em um arquivo RSL (Resource Specification Language) para execução em um grid com Globus. Resultados de execuções de aplicações reais e simulações demonstram que o uso de grid pode ser vantajoso.

Les événements spatio-temporels regroupent une large diversité de phénomènes comportant des caractéristiques propres. Par exemple, l’étude de flux migratoires se révèle ainsi très différente de l’étude de propagation de maladies. En effet, le domaine d’intérêt de la première porte sur le suivi des trajectoires, tandis que celui de la deuxième porte sur les facteurs de la propagation. De plus, chaque classe d’un problème spatio-temporel peut être abordée différemment, que l’on considère ou non un voisinage spatial, une caractérisation des objets d’étude unique ou multiple, ou bien une (in)dépendance entre les événements. Ainsi, les techniques de fouilles de données développées sont souvent restées spécifiques à une sous-classe de problème spatio-temporel, c’est-à-dire sous un ensemble restreint d’hypothèses.Or, pour réussir à dégager des connaissances nouvelles à partir de données, il est nécessaire d’élargir cet ensemble d’hypothèses, c’est-à-dire élargir le champs des possibles quant aux corrélations qu’il peut exister entre événements. Nous proposons donc une modélisation de ces phénomènes spatio-temporels permettant de prendre en compte plus de considérations que dans l’état de l’art. En outre, cette modélisation permet d’exprimer des événements qui existent dans les phénomènes d’érosion : un objet d’étude peut se diviser en plusieurs objets, ou fusionner avec d’autres objets pour n’en former qu’un seul. Plus précisément, nous modélisons les dynamiques spatio-temporelles sous la forme d’un unique graphe orienté, que la composante temporelle des problèmes rend acyclique, et dont les sommets sont attribués par plusieurs caractéristiques. / Spatio-temporal events denote a large range of phenomena with different characteristics. For example, migration flows studies appear to be very different from disease spread studies. Indeed, interestingness of the first relies on tracking trajectories, whereas the second is about finding the factors of spread. Moreover, each class of a spatio-temporal problem can be tackled differently, depending on which parameters are considered: the studied spatial neighbourhood, the number of characteristics associated with the objects, or whether events are supposed correlated or independent. As a result, data mining techniques are often specificto a sub-class of spatio-temporal problem, that is to say, to a limited set of hypothesis.In order to bring out new knowledge from data, it seems to be necessary to enlarge this set of hypothesis, that is to say, to widen the field of possibilities regarding correlations that may exist between events. For this, we propose a new model that allows to take into account more considerations than existing studies. For example, this representation allows to model the complex spatio-temporal dynamic of erosion phenomenon: an object can be split up in several other objects, or can merge with other objects into one. More precisely, we use a single directed graph, that becomes acyclic thanks to the temporal component of the problem, and that is attributed by several characteristics.

Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjecture. / In this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture.

Dans un premier chapitre, nous avons présenté un historique succinct de la chimiothérapie antivirale et l'utilisation d'analogues nucléos(t)idiques. Nous nous sommes focalisés en particulier sur les nucléosides phosphonates acycliques (ANP) en tant qu'antiviraux potentiels. Dans un second chapitre, nous avons décrit la synthèse de β-céto, β-hydroxylamino et β-O-(benzyl)hydroxylamino ANP dérivés de l'adénine et de la cytosine. Les isomèrs (R) et (S)-β-hydroxy-ANP ont été préparés par dédoublement du racémique correspondant avec le (S)-MPA et l'attribution des configurations absolues a été effectuée par RMN et calculs de modélisation moléculaire. Nous avons aussi développé une méthodologie de synthèse de β-azido-ANP, ces derniers étant utilisés pour la préparation de β-amino-ANP par hydrogénation catalytique. Dans un troisième chapitre, nous avons présenté la synthèse des 2H-azirine et cis-aziridne-ANP et examiné lʹ ouverture de cycle comme voie d'accès à des ANP α,β-fonctionnalisés. Les propriétés biologiques de ces nouveaux ANP ont été évaluées en culture cellulaire sur un certain nombre de virus à ADN et ARN. / In the first chapter, we presented a brief history of antiviral chemotherapy and use of nucleos(t)ide analogues, especially acyclic nucleoside phosphonates as potential antiviral agents. In the chapter-II we have successfully synthesized ¦Â-keto, ¦Â-hydroxylamino and ¦Â-O-(benzyl)hydroxylamino ANPs of adenine and cytosine derivatives. Then (R) and (S)-¦Â-hydroxy-ANPs were prepared via chiral resolution of racemic ¦Â-hydroxy-ANPs with (S)-MPA and assignment of absolute configuration was achieved using NMR and molecular modeling studies. We also developed a methodology for the synthesis of ¦Â-azido-ANPs and those were used for the preparation of ¦Â-amino-ANPs by catalytic hydrogenation. In third chapter, we synthesized 2H-azirine and cis-aziridine-ANPs and explored their ring opening to functionalized ¦Á,¦Â-ANPs. The novel ANPs obtained during this study were evaluated for their inhibitory effect on a number of DNA and RNA viruses in cell culture experiments.

Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros. / In this work we consider a problem from the Anthropology. The model of the societies and the marriages of individuals is done with mixed graphs and to find disjoint paths is a central question in the problem. The problem is NP-complete and W[1]-hard when it is considered a parameterized problem. Some subproblems that arise during the process to obtain a solution for the problem, involve disjoint paths and can be solved in polynomial time. We implemented some polynomial algorithms that are used in a tool developed to solve the problem in the Anthropology considered. Our solution worked well for the societies provided by our partners.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第21963号 / 工博第4618号 / 新制||工||1720(附属図書館) / 京都大学大学院工学研究科高分子化学専攻 / (主査)教授 山子 茂, 教授 辻井 敬亘, 教授 大内 誠 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM