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.

Crystallinity, Magnetic and Electrical Properties of Bi doped LaVO3

We report the results of crystal structure, magnetization and resistivity measurements of Bi doped LaVO3. X-ray diffraction (XRD) shows that if doping Bi in the La site is less than ten percent, the crystal structure of La1-xBixVO3 remains unchanged and its symmetry is orthorhombic. However, for higher Bi doping (>10%) composite compounds are found where the XRD patterns are characterized by two phases: LaVO3+V2O3. Energy-dispersive analysis of the x-ray spectroscopy (EDAX) results are used to find a proper atomic percentage of all samples. The temperature dependence of the mass magnetization of pure and single phase doped samples have transition temperatures from paramagnetic to antiferromagnetic region at TN=140 K. This measurement for bi-phasic samples indicates two transition temperatures, at TN=140 K (LaVO3) and TN=170 K (V2O3). The temperature dependence of resistivity reveals semiconducting behavior for all samples. Activation energy values for pure and doped samples are extracted by fitting resistivity versus temperature data in the framework of thermal activation process.

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.