Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

K -shell diagram and hypersatellite spectra of 4d transition elements

The K-shell diagram (K alpha(1,2) and K beta(1,3)) and hypersatellite (HS) (K-h alpha(1,2)) spectra of Y, Zr, Mo, and Pd have been measured with high energy-resolution using photoexcitation by 90 keV synchrotron radiation. Comparison of the measured and ab initio calculated HS spectra demonstrates the importance of quantum electrodynamical (QED) effects for the HS spectra. Phenomenological fits of the measured spectra by Voigt functions yield accurate values for the shift of the HS from the diagram lines, the splitting of the HS lines, and their intensity ratio. Good agreement with theory was found for all quantities except for the intensity ratio, which is dominated by the intermediacy of the coupling of the angular momenta. The observed deviations imply that our current understanding of the variation of the coupling scheme from LS to jj across the periodic table may require some revision.

Simulation and graph mining tools for improving gene mapping efficiency

Gene mapping is a systematic search for genes that affect observable characteristics of an organism. In this thesis we offer computational tools to improve the efficiency of (disease) gene-mapping efforts. In the first part of the thesis we propose an efficient simulation procedure for generating realistic genetical data from isolated populations. Simulated data is useful for evaluating hypothesised gene-mapping study designs and computational analysis tools. As an example of such evaluation, we demonstrate how a population-based study design can be a powerful alternative to traditional family-based designs in association-based gene-mapping projects. In the second part of the thesis we consider a prioritisation of a (typically large) set of putative disease-associated genes acquired from an initial gene-mapping analysis. Prioritisation is necessary to be able to focus on the most promising candidates. We show how to harness the current biomedical knowledge for the prioritisation task by integrating various publicly available biological databases into a weighted biological graph. We then demonstrate how to find and evaluate connections between entities, such as genes and diseases, from this unified schema by graph mining techniques. Finally, in the last part of the thesis, we define the concept of reliable subgraph and the corresponding subgraph extraction problem. Reliable subgraphs concisely describe strong and independent connections between two given vertices in a random graph, and hence they are especially useful for visualising such connections. We propose novel algorithms for extracting reliable subgraphs from large random graphs. The efficiency and scalability of the proposed graph mining methods are backed by extensive experiments on real data. While our application focus is in genetics, the concepts and algorithms can be applied to other domains as well. We demonstrate this generality by considering coauthor graphs in addition to biological graphs in the experiments.

Vibrational Spectra and Normal Coordinate Analysis of N-Methyl Thiourea

The infrared spectra of N-methylthiourea (NMTU) and its N-deuterated and S-methylated species were measured. Assignment of the infrared and Raman spectra of NMTU has been accomplished by correlation with thiourea and by use of infrared band shifts on N-deuteration as well as S-methylation. Normal coordinate analysis was performed for all the fundamentals of NMTU and NMTU-d3, the assignments obtained from the force field calculations being discussed in relation to those in other related thioureas and thioamides. The potential barriers to the internal rotations for the �NH2, �CH3, and �CN groups were estimated from the force constants.

Vibrational Spectra and Assignments for the Fundamental Vibrations of Imidazolidine-2-thione and -2-selenone

Infrared spectra of imidazolidine-2-thione (N,N?-ethylenethiourea, ETU) and its N,N?-deuterated (ETU-d2) and S-methylthiouronium iodides have been recorded from 4000 to 30 cm?1. Normal coordinate analyses of ETU and ETU-d2 have been made for all the fundamental frequencies, employing a Urey-Bradley potential function supplemented with valence type constants for the out of plane modes of the planar skeleton. Raman frequencies of ETU from literature have been utilised. The results of the vibrational analyses are discussed in relation to the group frequencies in structurally related molecules and frequency shifts on deuteration and S-methylation. The normal coordinate treatment is also performed for the planar vibrations of imidazolidine-2-selenone (N,N?-ethyleneselenourea, ESU) to propose assignments for ESU and so also to support the assignments of ETU.

Preparation and NMR spectra of four isomeric diformyl2.2]paracyclophanes (cyclophanes 66)

Four isomeric dialdehydes 4, readily available from cycloaddition of propiolic aldehyde (2) to 1,2,4,5-hexatetraene (1), were separated by chromatography and recrystallization, and were characterized by their spectroscopic data. The individual isomers can now be easily identified from their H-1 NMR spectra even if only one of them is present.

Relation between effective atomic charge and chemical shifts in X-ray absorption spectra of transition-metal compounds

Chemical shifts of K absorption discontinuities, Delta E, of several manganese, iron and cobalt oxides with the metal in the formal oxidation states between +2 and +4, have been measured. These data, together with data in the literature on other compounds of these metals, can be fitted into the expression Delta E=aq+bq2, where q is the effective atomic charge on the metal. Theoretical considerations also support this functional relationship between Delta E and q.