TOPOLOGICAL PROPERTIES OF TWISTED AND CROSSED CUBES
| Autor: | CHANG, CHIEN-PING, 張劍平 |
|---|---|
| Rok vydání: | 1998 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 86 An n-dimensional crossed cube is a variation of hypercube. In this thesis,we give a new shortest path routing algorithm. In comparison with Efe''salgorithm which generates one shortest path in O(n^2) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortestpath routing algorithm, we define a new performance measure of interconnection networks called edge congestion. Using our shortest pathrouting algorithm and assnming that message exchange between all pairs ofvertices are equally probable, we first show that the edge congestion ofcrossed cube is no larger than the edge congestion of hypercubes, then we prove that the bisection width and edge congestion of the crossed cube are2^(n-1) and 2^n, respectively. We also find a relationship between edge edge congestion and bisection width. Such relation provides some bounds of thesetwo parameters for some graphs. We also prove that wide diameter and fault diameter of crossed cubes are (n/2)+2. Furthermore, we study embedding ofcycles in crossed cubes and construct more types of cycles of an arbitrarylength at least four.Similarly, twisted cube is derived by changing some connections of hypercubeaccording to specific rules. We prove that wide diameter and fault diameterof twisted cubes are (n/2)+2. We also show that twisted cube is a pancyclicnetwork that is cycles of an arbitrary length at least four. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|