Dissertation > Excellent graduate degree dissertation topics show
On Path and Cycle Embeddings of Faulttolerant Networks
Author: DuZhengZhong
Tutor: XuJunMing
School: University of Science and Technology of China
Course: Applied Mathematics
Keywords: Hypercube networks University of Science and Technology of China Even cycle Point of failure Interconnection network Network topology Doctoral Dissertation Lemma Subnetworks Part of Fig.
CLC: O175.5
Type: PhD thesis
Year: 2006
Downloads: 124
Quote: 0
Read: Download Dissertation
Abstract
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 graphtheoretical 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}≤n1, every edge of Q_{n}F_{e} lies on a cycle of every even length from 6 to 2^{n} 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}≤n2 and every pair （u,v） of nodes in Q_{n}F_{e}, there exists a uvpath of length （?） with d_{Qn}（u, v）+2≤（?）≤2^{n}1, 2(（?）d_{Qn}（u,v）). If d_{Qn}（u,v）≥n1, there exists a uvpath of length d_{Qn}（u, v）.3. For any faulty node set F_{v} of Q_{n}（n≥5） with F_{v}=2n3, Q_{n}F_{v} contains a cycle of even length at least 2^{n}2F_{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}=2n4,F_{e}≤2n5, Q_{n}F_{v}F_{e} contains a cycle of even length at least 2^{n}2F_{v} provided every node of Q_{n}F_{v}F_{e} incidents with at least two nonfaulty 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 （n1）edgefaulttolerant edgebipancyclic; if n is even and FQ_{n} has at most n1 faulty edges, then every nonfaulty edge of FQ_{n} lies on a faultfree cycle of every even length from 4 to 2^{n} and every odd length from n+1 to 2^{n}1.2. For any set F_{e} of faulty edges of FQ_{n}（n≥3） with F_{e}≤2n3 and every node of FQ_{n}F_{e} incidents with at least two nonfaulty 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}≤n2, then any two nodes of FQ_{n}F_{e} are joined by a faultfree hamiltonian path; if n is odd and F_{e}≤n1, then any two different colored nodes of FQ_{n}F_{e} are joined by a faultfree hamiltonian path and any two same colored nodes of FQ_{n}F_{e} are joined by a faultfree path of length 2^{n}2.Conclusions and some problems to be studied further are in the fifth chapter.

Related Dissertations
 Periodic Solutions for Second Order Nonlinear Equations with Singular Vector φLaplacianLike Operators,O175
 IGMP packet Internet IPlevel topology measurement method study,TP393.02
 Existence of Solutions for the pLaplacian Equations with a HardySobolev Operator,O175.25
 About BorelCantelli Lemma Exttetion and Applaction,O211
 Hadoop Distributed File System (HDFS) Study Reliability and Optimization,TP316.4
 DTN in urban road network modeling and evaluation,TN929.5
 The Research and Design of Wireless Position System Based on ZIGBEE,TP212.9
 PostOlympic era Chinese sports newspaper Challenges and Strategies,G219.2F
 Improved algorithms of the network topology tomography,TN915.02
 Study on Idbased Signature Scheme Without Trusted Center,TN918.1
 Secondorder pulse homoclinic solution of differential equations and Boundary Value Problems,O175.8
 0.4kV Low Voltage Distribution Resource Management System,TM769
 Research and Application of Work and Operation Tickets in Power System,TM769
 Complexity of Public Transport Network in Tianjin,U491.17
 Jinan Vocational College campus network transformation,TP393.18
 Research on Router Level Network Topology Discovering Technology,TP393.02
 Design and Implementation of the SNMPBased Network Topology Discovery System,TP393.02
 Research about Topology Faulttolerance Scheme in Wireless Multihop Networks,TN929.5
 Design and Implement on IP Broadband Networking Optimization Support System,TN915.09
 The Research of Topology in Network on Chip,TN47
 A Solution for Two Elliptic Partial Differential Equations,O175.25
CLC: > Mathematical sciences and chemical > Mathematics > Mathematical Analysis > Differential equations, integral equations > Integral equation
© 2012 www.DissertationTopic.Net Mobile
