On Path And Cycle Embeddings Of Fault-tolerant Networks

Interconnection networks are usually represented by a graph G=(V, E), where the set of vertices V(G) represents processors, and the set of edges E(G) represents links between processors. Many interconnection network topologies have been proposed in the literature for the purpose of connecting hundreds or thousands of processing elements. Among these topologies the hypercubes, denoted by Q_n, is one of the most popular topologies. On the other hand, linear arrays and rings, which are two of the most fundamental networks for parallel and distributed computation, are suitable for developing simple algorithms with low communication costs. The implementation of these algorithms in the hypereubes is an embedding of paths and cycles into the hypercubes. Reliability is the most useful measure of a networks performance. It is useful to consider faulty networks because node faults or link faults may occur in networks. In this dissertation, we discuss the embedding of paths or cycles into the faulty hypercubes or the faulty folded hypercubes. It consists of five chapters, where Chapter Three and Chapter Four are main parts.In the first chapter, we introduce the background of our works.In the second chapter, we introduce graph-theoretical terminology and notation used in our discussion. We also introduce the concepts of fault tolerance and graph embedding. And the definitions of hypercubes and folded hypercubes. Then we list some known results on them.In the third chapter, we study the embedding of paths or cycles into faulty hypercubes. We get four main results as follows.1. For any set F_e of faulty edges of Q_n(n≥4) with |F_e|≤n-1, every edge of Q_n-F_e lies on a cycle of every even length from 6 to 2ⁿ inclusive provided all edges in F_e are not incident with the same vertex.2. For any set F_e of faulty edges of Q_n(n≥2) with |F_e|≤n-2 and every pair (u,v) of nodes in Q_n-F_e, there exists a uv-path of length (?) with d_Qn(u, v)+2≤(?)≤2ⁿ-1, 2|((?)-d_Qn(u,v)). If d_Qn(u,v)≥n-1, there exists a uv-path of length d_Qn(u, v).3. For any faulty node set F_v of Q_n(n≥5) with |F_v|=2n-3, Q_n-F_v contains a cycle of even length at least 2ⁿ-2|F_v|.4. For any set F_v of faulty nodes and set F_e of faulty edges of Q_n(n≥3) with |F_v|=2n-4,|F_e|≤2n-5, Q_n-F_v-F_e contains a cycle of even length at least 2ⁿ-2|F_v| provided every node of Q_n-F_v-F_e incidents with at least two non-faulty edges.In the forth chapter, we study the embedding of paths or cycles into faulty folded hypercubes. We get three results as follows.1. For n≥3, if n is odd, then FQ_n is (n-1)-edge-fault-tolerant edge-bipancyclic; if n is even and FQ_n has at most n-1 faulty edges, then every non-faulty edge of FQ_n lies on a fault-free cycle of every even length from 4 to 2ⁿ and every odd length from n+1 to 2ⁿ-1.2. For any set F_e of faulty edges of FQ_n(n≥3) with |F_e|≤2n-3 and every node of FQ_n-F_e incidents with at least two non-faulty edges, FQ_n-F_e contains a hamiltonian cycle.3. For any set F_e od faulty edges of FQ_n(n≥3), if n is even and |F_e|≤n-2, then any two nodes of FQ_n-F_e are joined by a fault-free hamiltonian path; if n is odd and |F_e|≤n-1, then any two different colored nodes of FQ_n-F_e are joined by a fault-free hamiltonian path and any two same colored nodes of FQ_n-F_e are joined by a fault-free path of length 2ⁿ-2.Conclusions and some problems to be studied further are in the fifth chapter.