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.

Evaluation of the profitability of fast-growing tropical trees.

The profitability of fast-growing trees was investigated in the northeastern and eastern provinces of Thailand. The financial, economic, and tentative environmental-economic profitability was determined separately for three fast-growing plantation tree species and for three categories of plantation managers: the private industry, the state (the Royal Forest Department) and the farmers. Fast-growing tree crops were also compared with teak (Tectona grandis), a traditional medium or long rotation species, and Para rubber (Hevea brasiliensis) which presently is the most common cultivated tree in Thailand. The optimal rotation for Eucalyptus camaldulensis pulpwood production was eight years. This was the most profitable species in pulpwood production. In sawlog production Acacia mangium and Melia azedarach showed a better financial profitability. Para rubber was more profitable and teak less profitable than the three fast-growing species. The economic profitability was higher than the financial one, and the tentative environmental-economic profitability was slightly higher than the economic profitability. The profitability of tree growing is sensitive to plantation yields and labour cost changes and especially to wood prices. Management options which aim at pulpwood production are more sensitive to input or output changes than those options which include sawlog production. There is an urgent need to improve the growth and yield data and to study the environmental impacts of tree plantations for all species and plantation types.

Heating values of mature trees.

The effective heating values of the above and below ground biomass components of mature Scots pine (Pinus sylvestris), Norway spruce (Picea abies), downy birch (Betula pubescens), silver birch (Betula pendula), grey alder (Alnus incana), black alder (Alnus glutinosa) and trembling aspen (Populus tremula) were studied. Each sample tree was divided into wood, bark and foliage components. Bomb calorimetry was used to determine the calorimetric heating values. The species is a significant factor in the heating value of individual tree components. The heating value of the wood proper is highest in conifers. Broad-leaved species have a higher heating value of bark than conifers. The species factor diminishes when the weighted heating value of crown, whole stems or stump-root-system are considered. The crown material has a higher heating value per unit weight in comparison with fuelwood from small-sized stems or wholetrees. The additional advantages of coniferous crown material are that it is a non-industrial biomass resource and is readily available. The variability of both the chemical composition and the heating value is small in any given tree component of any species. However, lignin, carbohydrate and extractive content were found to vary from one part of the tree to another and to correlate with the heating value.

Trees of Panama and Costa Rica

Book Review

Light scattering in random media with wavelength-scale structures : astronomical and industrial applications

Light scattering, or scattering and absorption of electromagnetic waves, is an important tool in all remote-sensing observations. In astronomy, the light scattered or absorbed by a distant object can be the only source of information. In Solar-system studies, the light-scattering methods are employed when interpreting observations of atmosphereless bodies such as asteroids, atmospheres of planets, and cometary or interplanetary dust. Our Earth is constantly monitored from artificial satellites at different wavelengths. With remote sensing of Earth the light-scattering methods are not the only source of information: there is always the possibility to make in situ measurements. The satellite-based remote sensing is, however, superior in the sense of speed and coverage if only the scattered signal can be reliably interpreted. The optical properties of many industrial products play a key role in their quality. Especially for products such as paint and paper, the ability to obscure the background and to reflect light is of utmost importance. High-grade papers are evaluated based on their brightness, opacity, color, and gloss. In product development, there is a need for computer-based simulation methods that could predict the optical properties and, therefore, could be used in optimizing the quality while reducing the material costs. With paper, for instance, pilot experiments with an actual paper machine can be very time- and resource-consuming. The light-scattering methods presented in this thesis solve rigorously the interaction of light and material with wavelength-scale structures. These methods are computationally demanding, thus the speed and accuracy of the methods play a key role. Different implementations of the discrete-dipole approximation are compared in the thesis and the results provide practical guidelines in choosing a suitable code. In addition, a novel method is presented for the numerical computations of orientation-averaged light-scattering properties of a particle, and the method is compared against existing techniques. Simulation of light scattering for various targets and the possible problems arising from the finite size of the model target are discussed in the thesis. Scattering by single particles and small clusters is considered, as well as scattering in particulate media, and scattering in continuous media with porosity or surface roughness. Various techniques for modeling the scattering media are presented and the results are applied to optimizing the structure of paper. However, the same methods can be applied in light-scattering studies of Solar-system regoliths or cometary dust, or in any remote-sensing problem involving light scattering in random media with wavelength-scale structures.