The effects of habitat edges and trampling intensity on vegetation in urban forests

Although changes in urban forest vegetation have been documented in previous Finnish studies, the reasons for these changes have not been studied explicitly. Especially, the consequences of forest fragmentation, i.e. the fact that forest edges receive more solar radiation, wind and air-borne nutrients than interiors have been ignored. In order to limit the change in urban forest vegetation we need to know why it occurs. Therefore, the effects of edges and recreational use of urban forests on vegetation were investigated together in this thesis to reveal the relative strengths of these effects and to provide recommendations for forest management. Data were collected in the greater Helsinki area (in the cities of Helsinki, Vantaa and Espoo, and in the municipalities of Sipoo and Tuusula) and in the Lahti region (in the city of Lahti and in the municipality of Hollola) by means of systematic and randomized vegetation and soil sampling and tree measurements. Sample plots were placed from the forest edges to the interiors to investigate the effects of forest edges, and on paths of different levels of wear and off these paths to investigate the effects of trampling. The natural vegetation of mesic and sub-xeric forest site types studied was sensitive both to the effects of the edge and to trampling. The abundances of dwarf shrubs and bryophytes decreased, while light- and nitrogen-demanding herbs and grasses - and especially Sorbus aucuparia – were favoured at the edges and next to the paths. Results indicated that typical forest site types at the edges are changing toward more nitrophilic vegetation communities. Covers of the most abundant forest species decreased considerably – even tens of percentages – from interiors to the edges indicating strong edge effects. These effects penetrated at least up to 50 m from the forest edges into the interiors, especially at south to west facing open edges. The effects of trampling were pronounced on paths and even low levels of trampling decreased the abundances of certain species considerably. The effects of trampling extended up to 8 m from path edges. Results showed that the fragmentation of urban forest remnants into small and narrow patches should be avoided in order to maintain natural forest understorey vegetation in the urban setting. Thus, urban forest fragments left within urban development should be at least 3 ha in size, and as circular as possible. Where the preservation of representative original forest interior vegetation is a management aim, closed edges with conifers can act as an effective barrier against solar radiation, wind and urban load, thereby restricting the effects of the edge. Tree volume at the edge should be at least 225-250 m3 ha-1 and the proportion of conifers (especially spruce) 80% or more of the tree species composition. Closed, spruce-dominated edges may also prevent the excessive growth of S. aucuparia saplings at urban forest edges. In addition, closed edges may guide people’s movements to the maintained paths, thus preventing the spontaneous creation of dense path networks. In urban areas the effects of edges and trampling on biodiversity may be considerable, and are important to consider when the aim of management is to prevent the development of homogeneous herb-grass dominated vegetation communities, as was observed at the investigated edges.

Ryssän koulussa : Suomalaiset Venäjän stipendiaatit autonomian aikana 1812-1917

Finnish scholarship students in Russia during the autonomy (1812-1917) During the autonomy in Finland (1809-1917), an attempt to improve the knowledge of the Russian language was made through special language university scholarships. With these scholarships the students could go and study the Russian language and acquire cultural knowledge in Russia. Other member countries on the edges of the Russian Empire, like Poland and the Baltic provinces, did not have similar programs. The first two scholars started their journey in 1812. A system of travel allowances was introduced in 1841. Between the years 1812- 1917 a total of almost 400 students studied in Russia. The studies mainly took place in Moscow. These scholarship students were called the Master s of Moscow ". In this paper, Finnish-Russian relations are studied based on the attitude towards the Russian language and the people who studied it in Finland. Although the attitude towards them was neutral in the beginning, in 1844 there was a strong change. Students of Russian, and especially the scholars, received the stigma of being unreliable and unpatriotic, a stigma they were never able to get rid of. The study of the Russian language was voluntary in Finnish schools between 1863 and 1872. Starting from 1890, however, the study of the Russian language was enforced. In doing so, the Russians attempted to unify the Empire, while the Finns had the illusion that they had their own state. Thus, Russia saw the language as a way to unify the Empire and Finns as an attempt to make them Russians. The purpose of studying in Russia was to improve the student s practical language skills and overall knowledge of the customs and culture of the country. Besides knowing the language, knowledge of Russian culture and customs is essential in understanding Russia and Russians; therefore, the studies of literature, geography and history have been noted in this research. Without knowledge it is difficult to develop understanding. After their studies, almost all of the scholars returned to Finland and did not continue their careers in Russia. They worked mainly as teachers and civil servants, and managed to improve the Finnish people s weak knowledge of Russian and Russia through teaching, translations of literature and newspaper articles. Through these scholars, it is possible to see how the attitudes towards the language have been closely related to the political history between Finland and Russia. The language became the subject of resistance and these attitudes were transferred to its students. In 1917, the study of Russia and the Russian language ended and it was no longer possible to use the acquired knowledge of language and country in independent Finland.

Perception of surface brightness

The human visual system has adapted to function in different lighting environments and responds to contrast instead of the amount of light as such. On the one hand, this ensures constancy of perception, for example, white paper looks white both in bright sunlight and in dim moonlight, because contrast is invariant to changes in overall light level. On the other hand, the brightness of the surfaces has to be reconstructed from the contrast signal because no signal from surfaces as such is conveyed to the visual cortex. In the visual cortex, the visual image is decomposed to local features by spatial filters that are selective for spatial frequency, orientation, and phase. Currently it is not known, however, how these features are subsequently integrated to form objects and object surfaces. In this thesis the integration mechanisms of achromatic surfaces were studied by psychophysically measuring the spatial frequency and orientation tuning of brightness perception. In addition, the effect of textures on the spread of brightness and the effect of phase of the inducing stimulus on brightness were measured. The novel findings of the thesis are that (1) a narrow spatial frequency band, independent of stimulus size and complexity, mediates brightness information (2) figure-ground brightness illusions are narrowly tuned for orientation (3) texture borders, without any luminance difference, are able to block the spread of brightness, and (4) edges and even- and odd-symmetric Gabors have a similar antagonistic effect on brightness. The narrow spatial frequency tuning suggests that only a subpopulation of neurons in V1 is involved in brightness perception. The independence of stimulus size and complexity indicates that the narrow tuning reflects hard-wired processing in the visual system. Further, it seems that figure-ground segregation and mechanisms integrating contrast polarities are closely related to the low level mechanisms of brightness perception. In conclusion, the results of the thesis suggest that a subpopulation of neurons in visual cortex selectively integrates information from different contrast polarities to reconstruct surface brightness.

Novel insights on functions of myotilin/palladin family members

Poikkijuovaisen luuranko- ja sydänlihaksen supistumisyksikkö, sarkomeeri, koostuu tarkoin järjestyneistä aktiini- ja myosiinisäikeistä. Rakenne eroaa muista solutyypeistä, joissa aktiinisäikeistö muovautuu jatkuvasti ja sen järjestyminen säätelee solun muotoa, solujakautumista, soluliikettä ja solunsisäisten organellien kuljetusta. Myotilin, palladin ja myopalladin kuuluvat proteiiniperheeseen, jonka yhteispiirteenä ovat immunoglobuliinin kaltaiset (Igl) domeenit. Proteiinit liittyvät aktiinitukirankaan ja niiden arvellaan toimivan solutukirangan rakenne-elementteinä ja säätelijöinä. Myotilinia ja myopalladinia ilmennetään poikkijuovaisessa lihaksessa. Sen sijaan palladinin eri silmukointimuotoja tavataan monissa kudostyypeissä kuten hermostossa, ja eri muodoilla saattaa olla solutyypistä riippuvia tehtäviä. Poikkijuovaisessa lihaksessa kaikki perheen jäsenet sijaitsevat aktiinisäikeitä yhdistävässä Z-levyssä ja ne sitovat Z-levyn rakenneproteiinia, -aktiniinia. Myotilingeenin pistemutaatiot johtavat periytyviin lihastauteihin, kun taas palladinin mutaatioiden on kuvattu liittyvän periytyvään haimasyöpään ja lisääntyneeseen sydäninfarktin riskiin. Tässä tutkimuksessa selvitettin myotilinin ja pallainin toimintaa. Kokeissa löydettiin uusia palladinin 90-92kDa alatyyppiin sitoutuvia proteiineja. Yksi niistä on aktiinidynamiikkaa säätelevä profilin. Profilinilla on kahdenlaisia tehtäviä; se edesauttaa aktiinisäikeiden muodostumista, mutta se voi myös eristää yksittäisiä aktiinimolekyylejä ja edistää säikeiden hajoamista. Solutasolla palladinin ja profilinin sijainti on yhtenevä runsaasti aktiinia sisältävillä solujen reuna-alueilla. Palladinin ja profilinin sidos on heikko ja hyvin dynaaminen, joka sopii palladinin tehtävään aktiinisäideiden muodostumisen koordinoijana. Toinen palladinin sitoutumiskumppani on aktiinisäikeitä yhteensitova -aktiniini. -Aktiniini liittää solutukirangan solukalvon proteiineihin ja ankkuroi solunsisäisiä viestintämolekyylejä. Sitoutumista välittävä alue on hyvin samankaltainen palladinissa ja myotilinissa. Luurankolihaksen liiallinen toistuva venytys muuttaa Z-levyjen rakennetta ja muotoa. Prosessin aikana syntyy uusia aktiinifilamenttejä sisältäviä tiivistymiä ja lopulta uusia sarkomeereja. Löydöstemme perusteella myotilinin uudelleenjärjestyminen noudattaa aktiinin muutoksia. Tämä viittaa siihen, että myotilin liittää yhteen uudismuodostuvia aktiinisäikeitä ja vakauttaa niitä. Myotilin saattaa myös ankkuroida viesti- tai rakennemolekyylejä, joiden tehtävänä on edesauttaa Z-levyjen uudismuodostusta. Tulostemme perusteella arvelemme, että myotilin toimii Z-levyjen rakenteen vakaajana ja aktiinisäikeiden säätelijänä. Palladinin puute johtaa sikiöaikaiseen kuolemaan hiirillä, mutta myotilinin puutoksella ei ole samanlaisia vaikutuksia. Tuotettujen myotilin poistogeenisten hiirten todetiin syntyvän ja kehittyvän normaalisti eikä niillä esiintynyt rakenteellisia tai toiminnallisia häiriöitä. Toisaalta aiemmissa kokeissa, joissa hiirille on siirretty ihmisen lihastautia aikaansaava myotilingeeni, nähdään samankaltaisia kuin sairailla ihmisillä. Näin ollen muuntunut myotilin näyttä olevan lihaksen toiminnalle haitallisempi kuin myotilinin puute. Myotilinin ja palladinin yhteisvaikutusta selvittääksemme risteytimme myotilin poistegeenisen hiiren ja hiirilinjan, joka ilmentää puutteellisesti palladinin 200 kDa muotoa. Puutteellisesti 200 kDa palladinia ilmentävien hiirten sydänlihaksessa todettiin vähäisiä hienorakenteen muutoksia, mutta risteytetyillä hiirillä tavattiin rakenteellisia ja toiminnallisia muutoksia myös luurankolihaksessa. Tulosten perusteella voidaan todeta, että palladinin 200 kDa muoto säätelee sydänlihassolujen rakennetta. Luurankolihaksessa sen sijaan myotilinilla ja palladinilla näyttäisi olevan päällekkäisiä tehtäviä.

Plant species diversity of buffer zones in agricultural landscapes: in search of determinants from the local to regional scale

Buffer zones are vegetated strip-edges of agricultural fields along watercourses. As linear habitats in agricultural ecosystems, buffer strips dominate and play a leading ecological role in many areas. This thesis focuses on the plant species diversity of the buffer zones in a Finnish agricultural landscape. The main objective of the present study is to identify the determinants of floral species diversity in arable buffer zones from local to regional levels. This study was conducted in a watershed area of a farmland landscape of southern Finland. The study area, Lepsämänjoki, is situated in the Nurmijärvi commune 30 km to the north of Helsinki, Finland. The biotope mosaics were mapped in GIS. A total of 59 buffer zones were surveyed, of which 29 buffer strips surveyed were also sampled by plot. Firstly, two diversity components (species richness and evenness) were investigated to determine whether the relationship between the two is equal and predictable. I found no correlation between species richness and evenness. The relationship between richness and evenness is unpredictable in a small-scale human-shaped ecosystem. Ordination and correlation analyses show that richness and evenness may result from different ecological processes, and thus should be considered separately. Species richness correlated negatively with phosphorus content, and species evenness correlated negatively with the ratio of organic carbon to total nitrogen in soil. The lack of a consistent pattern in the relationship between these two components may be due to site-specific variation in resource utilization by plant species. Within-habitat configuration (width, length, and area) were investigated to determine which is more effective for predicting species richness. More species per unit area increment could be obtained from widening the buffer strip than from lengthening it. The width of the strips is an effective determinant of plant species richness. The increase in species diversity with an increase in the width of buffer strips may be due to cross-sectional habitat gradients within the linear patches. This result can serve as a reference for policy makers, and has application value in agricultural management. In the framework of metacommunity theory, I found that both mass effect(connectivity) and species sorting (resource heterogeneity) were likely to explain species composition and diversity on a local and regional scale. The local and regional processes were interactively dominated by the degree to which dispersal perturbs local communities. In the lowly and intermediately connected regions, species sorting was of primary importance to explain species diversity, while the mass effect surpassed species sorting in the highly connected region. Increasing connectivity in communities containing high habitat heterogeneity can lead to the homogenization of local communities, and consequently, to lower regional diversity, while local species richness was unrelated to the habitat connectivity. Of all species found, Anthriscus sylvestris, Phalaris arundinacea, and Phleum pretense significantly responded to connectivity, and showed high abundance in the highly connected region. We suggest that these species may play a role in switching the force from local resources to regional connectivity shaping the community structure. On the landscape context level, the different responses of local species richness and evenness to landscape context were investigated. Seven landscape structural parameters served to indicate landscape context on five scales. On all scales but the smallest scales, the Shannon-Wiener diversity of land covers (H') correlated positively with the local richness. The factor (H') showed the highest correlation coefficients in species richness on the second largest scale. The edge density of arable field was the only predictor that correlated with species evenness on all scales, which showed the highest predictive power on the second smallest scale. The different predictive power of the factors on different scales showed a scaledependent relationship between the landscape context and local plant species diversity, and indicated that different ecological processes determine species richness and evenness. The local richness of species depends on a regional process on large scales, which may relate to the regional species pool, while species evenness depends on a fine- or coarse-grained farming system, which may relate to the patch quality of the habitats of field edges near the buffer strips. My results suggested some guidelines of species diversity conservation in the agricultural ecosystem. To maintain a high level of species diversity in the strips, a high level of phosphorus in strip soil should be avoided. Widening the strips is the most effective mean to improve species richness. Habitat connectivity is not always favorable to species diversity because increasing connectivity in communities containing high habitat heterogeneity can lead to the homogenization of local communities (beta diversity) and, consequently, to lower regional diversity. Overall, a synthesis of local and regional factors emerged as the model that best explain variations in plant species diversity. The studies also suggest that the effects of determinants on species diversity have a complex relationship with scale.

Effects of recreational use and fragmentation on the understorey vegetation and soil microbial communities of urban forests in southern Finland

The impacts of fragmentation and recreational use on the hemiboreal urban forest understorey vegetation and the microbial community of the humus layer (the phospholipid fatty acid (PLFA) pattern, microbial biomass and microbial activity, measured as basal respiration) were examined in the greater Helsinki area, southern Finland. Trampling tolerance of 1) herb-rich OMT, 2) mesic MT, and 3) sub-xeric VT forests (in decreasing order of fertility) was studied by comparing relative understorey vegetation cover (urban/untrampled reference ratio) of the three forest types. The trampling tolerance of forest vegetation increased with the productivity of the site (sub-xeric < mesic < herb-rich). Wear of understorey vegetation correlated positively with the number of residents (i.e., recreational pressure) around the forest patch. An increase of 15000 residents within a radius of 1 km around a forest patch was associated with ca. 30% decrease in the relative understorey vegetation cover. The cover of dwarf shrub Vaccinium myrtillus in particular decreased with increasing levels of wear. The cover of mosses in urban forests was less than half of that in untrampled reference areas. Cover of tree saplings, mainly Sorbus aucuparia, and some resilient herbs was higher than in the reference areas. In small urban forest fragments, broad-leaved trees, grasses and herbs were more abundant and mosses were scarcer than in larger urban forest areas. Thus, due to trampling and edge effects, resilient herb and grass species are replacing sensitive dwarf shrubs, mosses and lichens in urban forests. Differences in the soil microbial community structure were found between paths and untrampled areas and the effects of paths extended more than one meter from the paths. Paths supported approximately 25-30% higher microbial biomass with a transition zone of at least 1 m from the path edge. However, microbial activity per unit of biomass was lower on paths than in untrampled areas. Furthermore, microbial biomass and activity were 30-45% lower at the first 20 m into the forest fragments, due to low moisture content of humus near the edge. The decreased microbial activity detected at forest edges and paths implies decreased litter decomposition rates, and thus, a change in nutrient cycling. Changes in the decomposition and nutrient supply may in turn affect the diversity and function of plant communities in urban forests. Keywords: boreal forest vegetation, edge effects, phospholipid fatty acids, trampling, urban woodlands, wear

Environmental factors and uncertainty in fisheries management in the northern Baltic Sea

The Baltic Sea is a geologically young, large brackish water basin, and few of the species living there have fully adapted to its special conditions. Many of the species live on the edge of their distribution range in terms of one or more environmental variables such as salinity or temperature. Environmental fluctuations are know to cause fluctuations in populations abundance, and this effect is especially strong near the edges of the distribution range, where even small changes in an environmental variable can be critical to the success of a species. This thesis examines which environmental factors are the most important in relation to the success of various commercially exploited fish species in the northern Baltic Sea. It also examines the uncertainties related to fish stocks current and potential status as well as to their relationship with their environment. The aim is to quantify the uncertainties related to fisheries and environmental management, to find potential management strategies that can be used to reduce uncertainty in management results and to develop methodology related to uncertainty estimation in natural resources management. Bayesian statistical methods are utilized due to their ability to treat uncertainty explicitly in all parts of the statistical model. The results show that uncertainty about important parameters of even the most intensively studied fish species such as salmon (Salmo salar L.) and Baltic herring (Clupea harengus membras L.) is large. On the other hand, management approaches that reduce uncertainty can be found. These include utilising information about ecological similarity of fish stocks and species, and using management variables that are directly related to stock parameters that can be measured easily and without extrapolations or assumptions.

GATA Transcription Factors in Tissue Homeostasis and Pathology of the Gastrointestinal Tract and Liver

Mammalian gastrointestinal tract and liver are self-renewing organs that are able to sustain themselves due to stem cells present in their tissues. In constant, inflammation-related epithelial damage, vigorous activation of stem cells may lead to their uncontrolled proliferation, and further, to cancer. GATA-4, GATA-5, and GATA-6 regulate cell proliferation and differentiation in many mammalian organs. Lack of GATA-4 or GATA-6 leads to defective endodermal development and cell differentiation. GATA-4 and GATA-5 are considered the ones with tumor suppressive functions, whereas GATA-6 is more related to tumor promotion. In the digestive system their roles in inflammation and tumor-related molecular pathways remain unclear. In this study, we examined the GATA-related molecular pathways involved in normal tissue organization and renewal and in inflammation-related epithelial repair in the gastrointestinal tract and liver. The overall purpose of this study was to elucidate the relation of GATA factors to gastrointestinal and hepatic disease pathology and to evaluate their possible clinical significance in tumor biology. The results indicated distinct expression patterns for GATA-4, GATA-5, and GATA-6 in the human and murine gastrointestinal tract and liver, and their involvement in the regulation of intestine-specific genes. GATA-5 was confined to the intestines of suckling mice, suggesting an association with postnatal enzymatic changes. GATA-4 was upregulated in bowel inflammation concomitantly with TGF-β signaling. In gastrointestinal tumors, GATA-4 was restricted to benign neoplasias of the stomach, while GATA-6 was detected especially at the invasive edges of malignant tumors throughout the gut. In the liver, GATA-4 was upregulated in pediatric tumors along with erythropoietin (Epo), which was detected also in the sera of tumor patients. Furthermore, GATA-4 was enhanced in areas of vigorous hepatic regeneration in patients with tyrosinemia type I. These results suggest a central role for GATA-4 in pediatric tumor biology of the liver. To conclude, GATA-4, GATA-5, and GATA-6 are associated with normal gastrointestinal and hepatic development and regeneration. The appearance of GATA-4 along with TGF-β-signaling in the inflammatory bowel suggests a protective role in the response to inflammation-related epithelial destruction. However, in extremely malignant pediatric liver tumors, GATA-4 function is unlikely to be tumor-suppressing, probably due to the nature of the very primitive multipotent tumor cells. GATA-4, along with its possible downstream factor Epo, could be utilized as novel hepatic tumor markers to supplement the present diagnostics. They could also serve a function in future biological therapies for aggressive pediatric tumors.

Luonnonhoitopellot maatalousympäristön luonnon monimuotoisuuden edistämisessä

Luonnonhoitopellot lisättiin uutena vapaaehtoisena toimenpiteenä maatalouden ympäristötukeen vuonna 2009. Luonnonhoitopeltoihin kuuluvat monivuotiset nurmipellot sekä niitty-, riista- ja maisemakasveilla kylvetyt pellot. Toimenpiteen avulla pyritään suojelemaan ja lisäämään maatalousympäristön luonnon monimuotoisuutta sekä muun muassa vähentämään maatalouden ravinnehuuhtoumia. Vuonna 2010 luonnonhoitopeltoja oli yli seitsemän prosenttia Suomen viljelyalasta. Luonnonhoitopeltojen ympäristövaikutusten arvioiminen ja toimenpiteen kehittäminen on tärkeää, jotta toimenpiteeseen käytettävät varat eivät valu hukkaan. Tämän tutkimuksen tavoitteena oli selvittää, millainen merkitys luonnonhoitopelloilla on maatalousympäristön monimuotoisuuden kannalta; millaiset luonnonhoitopellot ovat monimuotoisuuden kannalta arvokkaimpia; ja kuinka toimenpidettä kannattaa kehittää. Kysymyksiin pyrittiin vastaamaan tutkimalla putkilokasvilajistoa, -lajirikkautta ja kasvillisuuden rakennetta erilaisilla luonnonhoitopelloilla, sekä vertaamalla luonnonhoitopeltojen kasvillisuutta pientareiden ja niittyjen kasvillisuuteen. Maastotyö luonnonhoitopelloilla tehtiin kesällä 2010 Uudenmaan ja Pohjois-Pohjanmaan ELY-keskusalueilla. Lisäksi tutkimuslohkoista kerättiin tietoja viljelijäkyselyn kautta. Niittypellot osoittautuivat tutkimuksessa lajirikkaimmaksi luonnonhoitopeltotyypiksi, mikä selittynee lähinnä sillä, että ne kylvetään heikosti kilpailukykyisellä siemenseoksella. Nurmi- ja niittypelloilla lohkon viljavuus korreloi negatiivisesti lajirikkauden kanssa. Lajikoostumukseltaan kaikki luonnonhoitopellot eroavat toisistaan sekä maatalousympäristön puoliluonnontilaisista elinympäristöistä, ja lisäävät siten monimuotoisuutta maisematasolla. Luonnonhoitopeltojen lajisto ei ole kuitenkaan suojelun kannalta erityisen arvokasta. Toimenpiteen maatalousympäristöä rikastuttavaa vaikutusta vähentää, että tällä hetkellä valtaosa luonnonhoitopelloista on monivuotisia nurmipeltoja. Luonnonhoitopeltojen siemenseoksia kehittämällä, perustamis- ja hoitomenetelmiä tutkimalla ja neuvontaan panostamalla voidaan lisätä luonnonhoitopeltojen arvoa niin luonnon, viljelijän kuin yhteiskunnankin kannalta.

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.

Distributed algorithms for edge dominating sets

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.

Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.

Accessibility as a determinant of opportunities : A case study from Peruvian Amazonia

Accessibility is a crucial factor for interaction between areas in economic, cultural, political and environmental terms. Therefore, information concerning accessibility is relevant for informed decision making, planning and research. The Loreto region in the Peruvian Amazonia provides an interesting scene for an accessibility study. Loreto is sparsely populated and because there are few roads in the region, in practice all movement and transportation happens along the river network. Due to the proximity of the Andes, river dynamics are strong and annual changes in water level combined with these dynamic processes constantly reshape accessibility patterns of the region. Selling non-timber forest products (NTFP) and agricultural products (AP) in regional centres is an important income source for local rain forest dwellers. Thus, accessibility to the centres is crucial for the livelihood of local population. -- In this thesis I studied how accessible the regional centre Iquitos is from other parts of Loreto. In addition, I studied the regional NTFP/AP trade patterns and compared them with patterns of accessibility. Based on GPS-measurements, using GIS, I created a time-distance surface covering Loreto. This surface describes the time-distance to Iquitos, along the river network. Based on interview material, I assessed annual changes to accessibility patterns in the region. The most common regional NTFP/AP were classified according to the amount of time they can be preserved, and based on the accessibility surface, I modelled a catchment area for each of these product classes. -- According to my results, navigation speeds vary considerably in different parts of the river network, depending on river types, vessels, flow direction and season. Navigating downstream is, generally, faster than upstream navigation. Thus, Iquitos is better accessible from areas situated south and south west of the city, like along the rivers Ucayali and Marañon. Differences in accessibility between different seasons are also substantial: during the dry season navigation is slower due to lower water levels and emerging sand bars. Regularly operating boats follow routes only along certain rivers and close to Iquitos transport facilities are more abundant than in more distant areas. Most of the products present in Iquitos market places are agricultural products, and the share of NTFP is significantly smaller. Most of the products were classified in product class 2, and the catchment area for these products is rather small. Many products also belonged to class 5, and the catchment area for these products reaches up to the edges of my study area, following the patterns of the river network. -- The accessibility model created in this study predicts travel times relatively well, although in some cases the modelled time-distances are substantially shorter than observed time-distances. This is partly caused by the fact that real-life navigation routes are more complicated than the modelled routes. Rain forest dwellers having easier access to Iquitos have more opportunities in terms of the products they decide to market. Thus, they can better take advantage of other factors affecting the market potential of different products. -- In all, understanding spatial variation in accessibility is important. In the Amazonian context it is difficult to combine the accessibility-related needs of the local dwellers with conservation purposes and the future challenge lies in finding solution that satisfy both of these needs.