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.

Region Connection Calculus: Composition Tables and Constraint Satisfaction Problems

Qualitative spatial reasoning (QSR) is an important field of AI that deals with qualitative aspects of spatial entities. Regions and their relationships are described in qualitative terms instead of numerical values. This approach models human based reasoning about such entities closer than other approaches. Any relationships between regions that we encounter in our daily life situations are normally formulated in natural language. For example, one can outline one's room plan to an expert by indicating which rooms should be connected to each other. Mereotopology as an area of QSR combines mereology, topology and algebraic methods. As mereotopology plays an important role in region based theories of space, our focus is on one of the most widely referenced formalisms for QSR, the region connection calculus (RCC). RCC is a first order theory based on a primitive connectedness relation, which is a binary symmetric relation satisfying some additional properties. By using this relation we can define a set of basic binary relations which have the property of being jointly exhaustive and pairwise disjoint (JEPD), which means that between any two spatial entities exactly one of the basic relations hold. Basic reasoning can now be done by using the composition operation on relations whose results are stored in a composition table. Relation algebras (RAs) have become a main entity for spatial reasoning in the area of QSR. These algebras are based on equational reasoning which can be used to derive further relations between regions in a certain situation. Any of those algebras describe the relation between regions up to a certain degree of detail. In this thesis we will use the method of splitting atoms in a RA in order to reproduce known algebras such as RCC15 and RCC25 systematically and to generate new algebras, and hence a more detailed description of regions, beyond RCC25.

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.

Ligand Design for Dual Property Single Molecule Magnets

This thesis describes two different approaches for the preparation of polynuclear clusters with interesting structural, magnetic and optical properties. Firstly, exploiting p-tert-butylcalix[4]arene (TBC4) macrocycles together with selected Ln(III) ions for the assembly of emissive single molecule magnets, and secondly the preparation and coordination of a chiral mpmH ligand with selected 3d transition metal ions, working towards the discovery of chiral polynuclear clusters. In Project 1, the coordination chemistry of the TBC4 macrocycle together with Dy(III) and Tb(III) afforded two Ln6[TBC4]2 complexes that have been structurally, magnetically and optically characterized. X-ray diffraction studies reveal that both complexes contain an octahedral core of Ln6 ions capped by two fully deprotonated TBC4 macrocycles. Although the unit cells of the two complexes are very similar, the coordination geometries of their Ln(III) ions are subtly different. Variable temperature ac magnetic susceptibility studies reveal that both complexes display single molecule magnet (SMM) behaviour in zero dc field and the energy barriers and associated pre-exponential factors for each relaxation process have been determined. Low temperature solid state photoluminescence studies reveal that both complexes are emissive; however, the f-f transitions within the Dy6 complex were masked by broad emissions from the TBC4 ligand. In contrast, the Tb(III) complex displayed green emission with the spectrum comprising four sharp bands corresponding to 5D4 → 7FJ transitions (where J = 3, 4, 5 and 6), highlighting that energy transfer from the TBC4 macrocycle to the Tb(III) ion is more effective than to Dy. Examples of zero field Tb(III) SMMs are scarce in the chemical literature and the Tb6[TBC4]2 complex represents the first example of a Tb(III) dual property SMM assembled from a p-tert-butylcalix[4]arene macrocycle with two magnetically derived energy barriers, Ueff of 79 and 63 K. In Project 2, the coordination of both enantiomers of the chiral ligand, α-methyl-2-pyridinemethanol (mpmH) to Ni(II) and Co(II) afforded three polynuclear clusters that have been structurally and magnetically characterized. The first complex, a Ni4 cluster of stoichiometry [Ni4(O2CCMe3)4(mpm)4]·H2O crystallizes in a distorted cubane topology that is well known in Ni(II) cluster chemistry. The final two Co(II) complexes crystallize as a linear mixed valence trimer with stoichiometry [Co3(mpm)6]·(ClO4)2, and a Co4 mixed valence complex [Co(II)¬2Co(III)2(NO3)2(μ-mpm)4(ONO2)2], whose structural topology resembles that of a defective double cubane. All three complexes crystallize in chiral space groups and circular dichroism experiments further confirm that the chirality of the ligand has been transferred to the respective coordination complex. Magnetic susceptibility studies reveal that for all three complexes, there are competing ferro- and antiferromagnetic exchange interactions. The [Co(II)¬2Co(III)2(NO3)2(μ-mpm)4(ONO2)2] complex represents the first example of a chiral mixed valence Co4 cluster with a defective double cubane topology.