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.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

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.

Using genetic algorithms for the single allocation hub location problem

Hub location problem is an NP-hard problem that frequently arises in the design of transportation and distribution systems, postal delivery networks, and airline passenger flow. This work focuses on the Single Allocation Hub Location Problem (SAHLP). Genetic Algorithms (GAs) for the capacitated and uncapacitated variants of the SAHLP based on new chromosome representations and crossover operators are explored. The GAs is tested on two well-known sets of real-world problems with up to 200 nodes. The obtained results are very promising. For most of the test problems the GA obtains improved or best-known solutions and the computational time remains low. The proposed GAs can easily be extended to other variants of location problems arising in network design planning in transportation systems.

Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Calculation of the magnetic field penetration depth for high-Tc cuprate superconductors based on the Interlayer Pair Tunneling model /

In this work, the magnetic field penetration depth for high-Tc cuprate superconductors is calculated using a recent Interlayer Pair Tunneling (ILPT) model proposed by Chakravarty, Sudb0, Anderson, and Strong [1] to explain high temperature superconductivity. This model involves a "hopping" of Cooper pairs between layers of the unit cell which acts to amplify the pairing mechanism within the planes themselves. Recent work has shown that this model can account reasonably well for the isotope effect and the dependence of Tc on nonmagnetic in-plane impurities [2] , as well as the Knight shift curves [3] and the presence of a magnetic peak in the neutron scattering intensity [4]. In the latter case, Yin et al. emphasize that the pair tunneling must be the dominant pairing mechanism in the high-Tc cuprates in order to capture the features found in experiments. The goal of this work is to determine whether or not the ILPT model can account for the experimental observations of the magnetic field penetration depth in YBa2Cu307_a7. Calculations are performed in the weak and strong coupling limits, and the efi"ects of both small and large strengths of interlayer pair tunneling are investigated. Furthermore, as a follow up to the penetration depth calculations, both the neutron scattering intensity and the Knight shift are calculated within the ILPT formalism. The aim is to determine if the ILPT model can yield results consistent with experiments performed for these properties. The results for all three thermodynamic properties considered are not consistent with the notion that the interlayer pair tunneling must be the dominate pairing mechanism in these high-Tc cuprate superconductors. Instead, it is found that reasonable agreement with experiments is obtained for small strengths of pair tunneling, and that large pair tunneling yields results which do not resemble those of the experiments.

Thermodynamic properties and Debye-Waller factor of fee materials

We have calculated the equation of state and the various thermodynamic properties of monatomic fcc crystals by minimizing the Helmholtz free energy derived in the high temperature limit for the quasiharmonic theory, QH, and the lowest-order (cubic and quartic), 'A2, anharmonic terms of the perturbation theory, PT. The total energy in each case is obtained by adding the static energy. The calculation of the thermal properties was carried out for a nearest-neighbour central-force model of the fcc lattice by means of the appropriate thermodynamic relations. We have calculated the lattice constant, the thermal expansion, the coefficient of volume expansion, the specific heat at constant volume and at constant pressure, the isothermal and adiabatic bulk moduli, and the Griineisen parameter, for the rare-gas solids Kr and Xe, and gold. Morse potential and modified Morse potential were each used to represent the atomic interaction for the three fcc materials. For most of the calculated thermodynamic properties from the QH theory, the results for Kr and Xe with the modified Morse potential show an improvement over the results for the Morse potential when compared with the experimental data. However, the results of the 'A 2 equation of state with the modified Morse potential are in good agreement with experiment only in the case of the specific heat at constant volume and at constant pressure. For Au we have calculated the lattice contribution from the QH and 'A 2 PT and the electronic contribution to the thermal properties. The electronic contribution was taken into account by using the free electron model. The results of the thermodynamic properties calculated with the modified Morse potential were similar to those obtained with the Morse potential. U sing the minimized equation of state we also calculated the Mossbauer recoilless fraction for Kr and Xe and the Debye-Waller factor (DWF) for Pb, AI, eu, Ag, and Au. The Mossbauer recoilless fraction was obtained for the above two potentials and Lennard-Jones potential. The L-J potential gives the best agreement with experiment for Kr. No experimental data exists for Xe. At low temperature the calculated DWF results for Pb, AI, and eu show a good agreement with experimental values, but at high temperature the experimental DWF results increase very rapidly. For Ag the computed values were below the expected results at all temperatures. The DWF results of the modified Morse potential for Pb, AI, eu and Ag were slightly better than those of the Morse potential. In the case of Au the calculated values were in poor agreement with experimental results. We have calculated the quasiharmonic phonon dispersion curves for Kr, Xe, eu, Ag, and Au. The calculated and experimental results of the frequencies agree quite well for all the materials except for Au where the longitudinal modes show serious discrepancies with the experimental results. In addition, the two lowest-order anharmonic contributions to the phonon frequency were derived using the Green's function method. The A 2 phonon dispersion curves have been calculated only for eu, and the results were similar to those of the QH dispersion curves. Finally, an expression for the Griineisen parameter "( has been derived from the anharmonic frequencies, and calculated for these materials. The "( results are comparable with those obtained from the thermodynamic definition.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

High-Spin and Emissive Molecular Materials: Synthesis and Characterization of New Polynuclear Ni(II) Complexes from the Use of Aromatic Schiff Bases as Bridging Ligands

The employment of the bridging/chelating Schiff bases, N-salicylidene-4-methyl-o-aminophenol (samphH2) and N-naphthalidene-2-amino-5-chlorobenzoic acid (nacbH2), in nickel cluster chemistry has afforded eight polynuclear Ni(II) complexes with new structural motifs, interesting magnetic and optical properties, and unexpected organic ligand transformations. In the present thesis, Chapter 1 deals with all the fundamental aspects of polynuclear metal complexes, molecular magnetism and optics, while research results are reported in Chapters 2 and 3. In the first project (Chapter 2), I investigated the coordination chemistry of the organic chelating/bridging ligand, N-salicylidene-4-methyl-o-aminophenol (samphH2). The general NiII/tBuCO2-/samphH2 reaction system afforded two new tetranuclear NiII clusters, namely [Ni4(samph)4(EtOH)4] (1) and [Ni4(samph)4(DMF)2] (2), with different structural motifs. Complex 1 possessed a cubane core while in complex 2 the four NiII ions were located at the four vertices of a defective dicubane. The nature of the organic solvent was found to be of pivotal importance, leading to compounds with the same nuclearity, but different structural topologies and magnetic properties. The second project, the results of which are summarized in Chapter 3, included the systematic study of a new optically-active Schiff base ligand, N-naphthalidene-2-amino-5-chlorobenzoic acid (nacbH2), in NiII cluster chemistry. Various reactions between NiX2 (X- = inorganic anions) and nacbH2 were performed under basic conditions to yield six new polynuclear NiII complexes, namely (NHEt3)[Ni12(nacb)12(H2O)4](ClO4) (3), (NHEt3)2[Ni5(nacb)4(L)(LH)2(MeOH)] (4), [Ni5(OH)2(nacb)4(DMF)4] (5), [Ni5(OMe)Cl(nacb)4(MeOH)3(MeCN)] (6), (NHEt3)2[Ni6(OH)2(nacb)6(H2O)4] (7), and [Ni6(nacb)6(H2O)3(MeOH)6] (8). The nature of the solvent, the inorganic anion, X-, and the organic base were all found to be of critical importance, leading to products with different structural topologies and nuclearities (i.e., {Ni5}, {Ni6} and {Ni12}). Magnetic studies on all synthesized complexes revealed an overall ferromagnetic behavior for complexes 4 and 8, with the remaining complexes being dominated by antiferromagnetic exchange interactions. In order to assess the optical efficiency of the organic ligand when bound to the metal centers, photoluminescence studies were performed on all synthesized compounds. Complexes 4 and 5 show strong emission in the visible region of the electromagnetic spectrum. Finally, the ligand nacbH2 allowed for some unexpected organic transformations to occur; for instance, the pentanuclear compound 5 comprises both nacb2- groups and a new organic chelate, namely the anion of 5-chloro-2-[(3-hydroxy-4-oxo-1,4-dihydronaphthalen-1-yl)amino]benzoic acid. In the last section of this thesis, an attempt to compare the NiII cluster chemistry of the N-naphthalidene-2-amino-5-chlorobenzoic acid ligand with that of the structurally similar but less bulky, N-salicylidene-2-amino-5-chlorobenzoic acid (sacbH2), was made.