Dissertation > Excellent graduate degree dissertation topics show

The Graph Embeddings in Faulty k Ary n Cubes

Author: FengKai
Tutor: WangShiYing
School: Shanxi University
Course: Operational Research and Cybernetics
Keywords: Embedding cycles Faulty elements Fault-tolerance k Ary n cubes
CLC: O157.5
Type: Master's thesis
Year: 2011
Downloads: 16
Quote: 0
Read: Download Dissertation

Abstract


In many parallel computer systems, processors are connected based on an intercon-nection network, popular instances of interconnection networks include Petersen graphs, hypercubes and k ary n cubes. As having many desirable properties, such as ease of im-plementation, low-latency and high-bandwidth interprocessor communication, the k ary n cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. The k ary n cube, denoted by Qnk (k;≥2, n≥1), is a graph consisting of kn vertices. The set of vertices V(Qnk)=｛u0u1…un-1:0≤ui≤k-1,0≤i≤n-1｝. Two vertices u=u0u1…un-1 and v =v0v1…vn-1 are adjacent if and only if there exists an integer j∈｛0,1,…,n-1｝such that uj=vj±1(mod k) and ui=ui for every i∈｛0,1,…,n-l｝\｛j｝.In multiprocessor systems, failures in networks are inevitable. If a network with faulty elements still have some good properties, then the network is faulty-tolerant. Conditional fault-tolerance is to restrict fault distributions in an interconnection network. It means that each vertex in faulty interconnection networks is incident with at least two healthy edges. Graph embedding is a technique that maps a logical graph into a host graph. Many applications, such as architecture simulation, processor allocation, can be modelled as graph embedding. Many graph embeddings take paths and cycles as guest graphs because they are the common structures used to model linear arrays in parallel processing. In this paper,we study the problem of embedding cycles in faulty k ary n cubes. The article is divided into four chapters:In Chapter 1, we introduce some useful basic concepts.In Chapter 2, we consider the longest cycle embedding problem in faulty k ary 2 cubes. Given an even k≥4, let (V1, V2) be the bipartition of the k ary 2 cube and fv1, fv2 be the numbers of faulty vertices in V1 and V2, respectively. We prove that there exists a cycle of length k2 - 2max｛fv1,fv2｝in the k ary 2 cube with at most two faults. This result is optimal with respect to the number of faults tolerated.In Chapter 3, we consider the cycle embedding problem in 3 ary n cubes with condi-tional edge faults. We show that there exists a cycle of any length from 3 to 3n in a 3 ary n cube with at most 2n - 1 edge faults in which each vertex is incident with at least two healthy edges for n≥2 if the subgraph induced by the fault edges is acyclic. This result is optimal with respect to the number of faults tolerated. In Chapter 4, we consider the cycle embedding problem in k ary 2 cubes with condi-tional edge faults and show that there exists a cycle of every even length from 4 toκ2 in a k ary 2 cube with at most 3 edge faults in which each vertex is incident with at least two healthy edges for evenκ≥4. This result is optimal with respect to the number of faults tolerated.

Related Dissertations

  1. Polarized-Light/Geomagnetism/GPS/SINS Integrated Navigation Algorithm,V249.328
  2. The Research of Fault-Tolerant Techniques for Parallel/Distributed Network Simulator PDNS,TP302.8
  3. Research on Checkpointing in Mobile Computing Environment and Modeling with Petri Nets,TP301.1
  4. ARM Embedded System for H.264 decoding research,TP368.1
  5. E-commerce based on Mobile Agent Communication Research mailbox,TP393.09
  6. High-performance storage system is a key technology research,TP333
  7. Fault-tolerant real-time systems based on energy-efficient scheduling algorithm,TP316.2
  8. Local tolerance studies twisted cube LTQ_n,O157.5
  9. Fault-tolerant software fault-tolerant computer systems design and implementation,TP302.8
  10. Edge Fault Tolerance of Super Edge Connectivity for Several Families of Interconnection Networks,O157.5
  11. Research on Fault Tolerance Technique for Eec Based on BIT,V233.7
  12. Scheme of CAN Bus Application Layer Protocol and Fault Tolerant Technology Research,TP273
  13. The Design and Implement of Communication Between Core Modules in High Dependable Embedded Computer System Based on ARM7,TP274.2
  14. The Research on Fault Tolerant Multicast in Hypercube Network,TP393.02
  15. Transaction -oriented fault-tolerant computer technology research and implementation of arbitration,TP302.8
  16. Design and Implementation of Fault-Tolerant Parallel Algorithm for On-board Computer,TP302.8
  17. Research about Topology Fault-tolerance Scheme in Wireless Multi-hop Networks,TN929.5
  18. Dynamic Reconfigurable FPGA- based timing circuit line fault detection and fault-tolerant design,TH165.3
  19. The Research of Some Relay Nodes Placement in Wireless Sensor Networks,TN929.5
  20. Wireless sensor networks tolerant routing of double points,TP212.9
  21. Research and Simulated Implementation of Intelligent Fault-Tolerant QoS Routing Mechanisms in NGI,TP393.02

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile