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.

Living on the edge : Population genetics of Finno-Ugric-speaking humans in North Eurasia

The major aim of this thesis was to examine the origins and distribution of uniparental and autosomal genetic variation among the Finno-Ugric-speaking human populations living in Boreal and Arctic regions of North Eurasia. In more detail, I aimed to disentangle the underlying molecular and population genetic factors which have produced the patterns of uniparental and autosomal genetic diversity in these populations. Among Finno-Ugrics the genetic amalgamation and clinal distribution of West and East Eurasian gene pools were observed within uniparental markers. This admixture indicates that North Eurasia was colonized through Central Asia/ South Siberia by human groups already carrying both West and East Eurasian lineages. The complex combination of founder effects, gene flow and genetic drift underlying the genetic diversity of the Finno-Ugric- speaking populations were emphasized by low haplotype diversity within and among uniparental and biparental markers. A high prevalence of lactase persistence allele among the North Eurasian Finno- Ugric agriculturalist populations was also shown indicating a local adaptation to subsistence change with lactose rich diet. Moreover, the haplotype background of lactase persistence allele among the Finno- Ugric-speakers strongly suggested that the lactase persistence T-13910 mutation was introduced independently more than once to the North Eurasian gene pool. A significant difference in genetic diversity, haplotype structure and LD distribution within the cytochrome P450 CYP2C and CYP2D regions revealed the unique gene pool of the Finno-Ugric Saami created mainly by population genetic processes compared to other Europeans and sub-Saharan Mandenka population. From all studied populations the Saami showed also significantly the highest allele frequency of a CYP2C19 gene mutation causing variable drug reactions. The diversity patterns observed within CYP2C and CYP2D regions emphasize the strong effect of demographic history shaping genetic diversity and LD especially among such small and constant size populations as the Finno-Ugric-speaking Saami. Moreover, the increased LD in Saami due to genetic drift and/or admixture was shown to offer an advantage for further attempts to identify alleles associated to common complex pharmacogenetic traits.

Population dynamics of blue mussels in a variable environment at the edge of their range

Spatial and temporal variation in the abundance of species can often be ascribed to spatial and temporal variation in the surrounding environment. Knowledge of how biotic and abiotic factors operate over different spatial and temporal scales in determining distribution, abundance, and structure of populations lies at the heart of ecology. The major part of the current ecological theory stems from studies carried out in central parts of the distributional range of species, whereas knowledge of how marginal populations function is inadequate. Understanding how marginal populations, living at the edge of their range, function is however in a key position to advance ecology and evolutionary biology as scientific disciplines. My thesis focuses on the factors affecting dynamics of marginal populations of blue mussels (Mytilus edulis) living close to their tolerance limits with regard to salinity. The thesis aims to highlight the dynamics at the edge of the range and contrast these with dynamics in more central parts of the range in order to understand the potential interplay between the central and the marginal part in the focal system. The objectives of the thesis are approached by studies on: (1) factors affecting regional patterns of the species, (2) long-term temporal dynamics of the focal species spaced along a regional salinity gradient, (3) selective predation by increasing populations of roach (Rutilus rutilus) when feeding on their main food item, the blue mussel, (4) the primary and secondary effects of local wave exposure gradients and (5) the role of small-scale habitat heterogeneity as determinants of large-scale pattern. The thesis shows that populations of blue mussels are largely determined by large scale changes in sea water salinity, affecting mainly recruitment success and longevity of local populations. In opposite to the traditional view, the thesis strongly indicate that vertebrate predators strongly affect abundance and size structure of blue mussel populations, and that the role of these predators increases towards the margin where populations are increasingly top-down controlled. The thesis also indicates that the positive role of biogenic habitat modifiers increases towards the marginal areas, where populations of blue mussels are largely recruitment limited. Finally, the thesis shows that local blue mussel populations are strongly dependent on high water turbulence, and therefore, dense populations are constrained to offshore habitats. Finally, the thesis suggests that ongoing sedimentation of rocky shores is detrimental for the species, affecting recruitment success and post-recruit survival, pushing stable mussel beds towards offshore areas. Ongoing large scale changes in the Baltic Sea, especially dilution processes with attendant effects, are predicted to substantially contract the distributional range of the mussel, but also affect more central populations. The thesis shows that in order to understand the functioning of marginal populations, research should (1) strive for multi-scale approaches in order to link ecosystem patterns with ecosystem processes, and (2) challenge the prevailing tenets that origin from research carried out in central areas that may not be valid at the edge.

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.

When sharing becomes a liability: An intellectual capital approach to describing the dichotomy of knowledge protection versus sharing in intra- and interorganizational relationships

The tension created when companies are collaborating with competitors – sometimes termed co-opetition - has been subject of research within the network approach. As companies are collaborating with competitors, they need to simultaneously share and protect knowledge. The opportunistic behavior and learning intent of the partner may be underestimated, and collaboration may involve significant risks of loss of competitive edge. Contrastingly, the central tenet within the Intellectual Capital approach is that knowledge grows as it flows. The person sharing does not lose the knowledge and therefore knowledge has doubled from a company’s point of view. Value is created through the interplay of knowledge flows between and within three forms of intellectual capital: human, structural and relational capital. These are the points of departure for the research conducted in this thesis. The thesis investigates the tension between collaboration and competition through an Intellectual Capital lens, by identifying the actions taken to share and protect knowledge in interorganizational collaborative relationships. More specifically, it explores the tension in knowledge flows aimed at protecting and sharing knowledge, and their effect on the value creation of a company. It is assumed, that as two companies work closely together, the collaborative relationship becomes intertwined between the two partners and the intellectual capital flows of both companies are affected. The research finds that companies commonly protect knowledge also in close and long-term collaborative relationships. The knowledge flows identified are both collaborative and protective, with the result that they sometimes are counteracting and neutralize each other. The thesis contributes to the intellectual capital approach by expanding the understanding of knowledge protection in interorganizational relationships in three ways. First, departing from the research on co-opetition it shifts the focus from the internal view of the company as a repository of intellectual capital onto the collaborative relationships between competing companies. Second, instead of the traditional collaborative and sharing point of departure, it takes a competitive and protective perspective. Third, it identifies the intellectual capital flows as assets or liabilities depending on their effect on the value creation of the company. The actions taken to protect knowledge in an interorganizational relationship may decrease the value created in the company, which would make them liabilities.

Increasing Knowledge Focus - a Means for Entrepreneurs to Remain on a Growth Path: Essays on the Role and Nature of Knowledge Management in Finnish SMEs (summary section only)

This study explores the role and nature of knowledge management (KM) in small and medium-sized companies (SMEs). Even though the role of knowledge as a competitive advantage is commonly recognized in the SME sector, almost no attention has been paid to the managing and developing of knowledge in SMEs. This thesis consists of three different sub-studies that were reported in four individual essays. The results of the questionnaire study indicate that nearly all companies that responded to the questionnaire (N = 108) found intangible assets, i.e. knowledge resources to be their main source of competitive advantage. However, only less than a third of the companies actively deal with knowledge management. The results also indicate a significant correlation between activity in knowledge management and sustainable organic growth of the company. The interview study (N = 10) explored the context and motives of the SMEs for managing their intangible assets, and the concrete practices of knowledge management. It turned out that KM facilitated change management, clarification of the vision and new strategy formulation. All the interviewed companies were aiming at improved innovation process, new ways of doing business and attaining an increased “knowledge focus” in their business. Nearly all also aspired to grow significantly. Thus, KM provides a strategy for these SMEs to guarantee their survival and sustainability in the turbulent markets. The action research was a process to assess and develop intangible resources in three companies. The experienced benefits were the clarification of future focus and strategy, creation of a common language to discuss strategic issues within the company, as well as improved balance of different categories of intangible assets. After the process all the case companies had developed in the chosen key areas. Thus, by systematic knowledge management the implementation of new strategic orientation (knowledge focusing) was facilitated. The findings can be summarized in two main points. First, knowledge management seems to serve the purpose of change, renewal and new strategic orientation in the SMEs. It also seems to be closely related to organic growth and innovation. All of these factors can be considered dimensions of entrepreneurship. Second, the conscious development of intangible assets can increase the balance of different categories of intangible assets and the overall knowledge focusing of business. In the case companies, this in turn facilitated the path to the improved overall performance.

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.