Topological properties of the class of hypercube-like graphs

Abstract

In parallel computing, processors are connected into various interconnection networks. A number of network topologies have been suggested by several researchers. Among these topologies, the hypercube network is one of the most popular topologies due to many of its attractive properties. However, the hypercube is not best possible for its resources. Variations of the hypercube network have been discovered which further improve some of its properties. But due to a lack of the unified model, results on one network are hard to apply to other variants. We have chosen a class of hypercube variants, called the class of hypercube-like graphs. The class of hypercube-like graphs is proposed for the first time by Vaidya et al. The class retains many attractive properties of hypercube and contains most important hypercube variants. In this thesis, we introduce the class of HL-graphs and present the graph-theoretic properties of the class. We present two oblivious routing algorithms for the HL-graphs. The dimension reducing algorithm is a natural extension of the e-cube routing algorithm. The dimension detouring algorithm runs with look-ahead information. Both algorithms find a routing path at most n steps for an n-dimensional HL-graph. And we also present a deadlock-free wormhole routing algorithm for the HL-graphs. We introduce a new interconnection network topology, called a randomly twisted cube. We prove that the average distance of a randomly twisted cube is O(n/log n), which is asymptotically optimal. Our experiments show that the randomly twisted cube works well. We also show that the fault diameter of the HL-graph is at most n+[log(n-1)]. And we show that HL-graphs are hamiltonian. This result gives a positive answer to Vaidya``s conjecture. All HL-graphs are hamiltonian-connected or hamiltonian-laceable. And we show that HL-graphs are bipancyclic. We also show that HL-graphs retain hamiltonian properties when some edges or vertices are faulty.