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.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

SYNTHESIS OF CYCLIC AZOBENZENE ANALOGUES FOR INCORPORATION INTO OLIGONUCLEOTIDES, PEPTIDES AND POLYMERS

(A) In recent years, considerable amount of effort has contributed towards enhancing our understanding of the new photoswitch, cyclic azobenzene, particularly from the theoretical point of view. However, the challenging part with this system was poor efficiency of its synthesis from 2,2’- dinitrodibenzyl and lack of effective methods for further modification which would be useful to incorporate this system into biomolecules as a photoswitch. We report the synthesis of cyclic azobenzene and analogues from 2,2’-dinitrodibenzyl, which would allow for further incorporation of this cyclic azobenzene into biomolecules. Reaction of 2,2’-dinitrodibenzyl with zinc metal powder in the presence of triethylammonium formate buffer (pH-9.5) gave a cyclic azoxybenzene, 11,12-dihydrodibenzo[c,g][1,2]diazocine-5-oxide. The latter compound was converted into cyclic azobenzene analogues (bromo-, chloro-, cyano-, and carboxyl) through subsequent transformations. The carboxylic acid analogue was reacted with D-threoninol to give the corresponding amide, which readily undergoes photo-isomerization upon illumination with light. Upon illumination with light at 400 nm, approximately 70% of cis- isomer of amide was isomerized to trans- isomer. It was observed that cis- to trans- isomerization reached the maximum steady state of light transmission after approximately 40 min, whereas the trans- to cis- isomerization approximately acquired in 2 h to regain full recovery of light transmission. Cyclic azobenzene phosphoramidite was synthesized from DMT-protected D-threoninol linked cyclic azobenzene. (B) In recent years, there has been considerable interest invested towards the synthesis of azobenzene analogues for incorporation into proteins. Among the many azobenzene analogues, the synthesis of bi-functional cyclic azobenzene analogues for the incorporation into proteins is relatively new. In this thesis, we report the synthesis of a cyclic azobenzene biscarboxylic acid from 4-(bromomethyl)benzonitrile. (C) Azobenzene has been widely used in the field of polymer science to study the surface morphology and surface properties of polymers. In this thesis, we report the incorporation of cyclic azobenzene into a commercial polymer 2- (hydroxyethyl)methacrylate. Samples collected after 24 h from the reaction solution showed approximately 9% of incorporation of cyclic azobenzene into polymer compared to samples collected after 10 h, which showed approximately 6% incorporation.

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.