A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Inverse problem for the wave equation : partial data and novel boundary sources

An inverse problem for the wave equation is a mathematical formulation of the problem to convert measurements of sound waves to information about the wave speed governing the propagation of the waves. This doctoral thesis extends the theory on the inverse problems for the wave equation in cases with partial measurement data and also considers detection of discontinuous interfaces in the wave speed. A possible application of the theory is obstetric sonography in which ultrasound measurements are transformed into an image of the fetus in its mother's uterus. The wave speed inside the body can not be directly observed but sound waves can be produced outside the body and their echoes from the body can be recorded. The present work contains five research articles. In the first and the fifth articles we show that it is possible to determine the wave speed uniquely by using far apart sound sources and receivers. This extends a previously known result which requires the sound waves to be produced and recorded in the same place. Our result is motivated by a possible application to reflection seismology which seeks to create an image of the Earth s crust from recording of echoes stimulated for example by explosions. For this purpose, the receivers can not typically lie near the powerful sound sources. In the second article we present a sound source that allows us to recover many essential features of the wave speed from the echo produced by the source. Moreover, these features are known to determine the wave speed under certain geometric assumptions. Previously known results permitted the same features to be recovered only by sequential measurement of echoes produced by multiple different sources. The reduced number of measurements could increase the number possible applications of acoustic probing. In the third and fourth articles we develop an acoustic probing method to locate discontinuous interfaces in the wave speed. These interfaces typically correspond to interfaces between different materials and their locations are of interest in many applications. There are many previous approaches to this problem but none of them exploits sound sources varying freely in time. Our use of more variable sources could allow more robust implementation of the probing.

Tree mortality, fire scar formation and regeneration 8 years after low-intensity fire in managed Pinus sylvestris stands

Fire is an important driver of the boreal forest ecosystem, and a useful tool for the restoration of degraded forests. However, we lack knowledge on the ecological processes initiated by prescribed fires, and whether they bring about the desired restoration effects. The purpose of this study was to investigate the impacts of low-intensity experimental prescribed fires on four ecological processes in young commercial Scots pine (Pinus sylvestris) stands eight years after the burning. The processes of interest were tree mortality, dead wood creation, regeneration and fire scar formation. These were inventoried in twelve study plots, which were 30 m x 30 m in size. The plots belonged to two different stand age classes: 30-35 years or 45 years old at the time of burning. The study was partly a follow-up of study plots researched by Sidoroff et al. (2007) one year after burning in 2003. Tree mortality increased from 183 stems ha-1 in 2003 to 259 stems ha-1 in 2010, corresponding to 15 % and 21 % of stem number respectively. Most mortality was experienced in the stands of the younger age class, in smaller diameter classes and among species other than Scots pine. By 2010, the average mortality of Scots pine per plot was 18%, but varied greatly ranging from 0% to 63% of stem number. Delayed mortality, i.e. mortality that occurred between 2 and 8 years after fire, seemed to become more important with increasing diameter. The input of dead wood also varied greatly between plots, from none to 72 m3 ha-1, averaging at 12 m3 ha-1. The amount of fire scarred trees per plot ranged from none to 20 %. Four out of twelve plots (43 %) did not have any fire scars. Scars were on average small: 95% of scars were less than 4 cm in width, and 75% less than 40 cm in length. Owing to the light nature of the fire, the remaining overstorey and thick organic layer, regeneration was poor overall. The abundance of pine and other seedlings indicated a viable seed source existed, but the seedlings failed to establish under dense canopy. The number of saplings ranged from 0 to 12 333 stems ha-1. The results of this study indicate that a low intensity fire does not necessarily initiate the ecological processes of tree mortality, dead wood creation and regeneration in the desired scale. Fire scars, which form the basis of fire dating in fire history studies, did not form in all cases.