Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Evolutionary Origin and Maintenance of Sociality in the Small Carpenter Bees

Many arthropods exhibit behaviours precursory to social life, including adult longevity, parental care, nest loyalty and mutual tolerance, yet there are few examples of social behaviour in this phylum. The small carpenter bees, genus Ceratina, provide important insights into the early stages of sociality. I described the biology and social behaviour of five facultatively social species which exhibit all of the preadaptations for successful group living, yet present ecological and behavioural characteristics that seemingly disfavour frequent colony formation. These species are socially polymorphic with both / solitary and social nests collected in sympatry. Social colonies consist of two adult females, one contributing both foraging and reproductive effort and the second which remains at the nest as a passive guard. Cooperative nesting provides no overt reproductive benefits over solitary nesting, although brood survival tends to be greater in social colonies. Three main theories explain cooperation among conspecifics: mutual benefit, kin selection and manipulation. Lifetime reproductive success calculations revealed that mutual benefit does not explain social behaviour in this group as social colonies have lower per capita life time reproductive success than solitary nests. Genetic pedigrees constructed from allozyme data indicate that kin selection might contribute to the maintenance of social nesting -, as social colonies consist of full sisters and thus some indirect fitness benefits are inherently bestowed on subordinate females as a result of remaining to help their dominant sister. These data suggest that the origin of sociality in ceratinines has principal costs and the great ecological success of highly eusociallineages occurred well after social origins. Ecological constraints such as resource limitation, unfavourable weather conditions and parasite pressure have long been considered some of the most important selective pressures for the evolution of sociality. I assessed the fitness consequences of these three ecological factors for reproductive success of solitary and social colonies and found that nest sites were not limiting, and the frequency of social nesting was consistent across brood rearing seasons. Local weather varied between seasons but was not correlated with reproductive success. Severe parasitism resulted in low reproductive success and total nest failure in solitary nests. Social colonies had higher reproductive success and were never extirpated by parasites. I suggest that social nesting represents a form of bet-hedging. The high frequency of solitary nests suggests that this is the optimal strategy when parasite pressure is low. However, social colonies have a selective advantage over solitary nesting females during periods of extreme parasite pressure. Finally, the small carpenter bees are recorded from all continents except Antarctica. I constructed the first molecular phylogeny of ceratinine bees based on four gene regions of selected species covering representatives from all continents and ecological regions. Maximum parsimony and Bayesian Inference tree topology and fossil dating support an African origin followed by an Old World invasion and New World radiation. All known Old World ceratinines form social colonies while New World species are largely solitary; thus geography and phylogenetic inertia are likely predictors of social evolution in this genus. This integrative approach not only describes the behaviour of several previously unknown or little-known Ceratina species, bu~ highlights the fact that this is an important, though previously unrecognized, model for studying evolutionary transitions from solitary to social behaviour.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.