Edge-Fault-Tolerant Path/Cycle Embedding on Three Classes of Cayley Graphs
Date Issued
2008
Date
2008
Author(s)
Tsai, Ping-Ying
Abstract
Advances in technology, especially the advent of VLSI circuit technology, have made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. One crucial step on designing a large-scale parallel and distributed system is to determine the topology of the interconnection network (network for short). The network topology not only affects the hardware architecture but also the nature of theystem software that can be used in a parallel and distributed system. A number of network topologies have been proposed. Among them, a class of graphs called Cayley graphs is of interest for the design and analysis of interconnection networks.or interconnection networks, the problem of simulating one network by another is modelled as a network embedding problem. Linear arrays and rings, which are two of theost fundamental interconnection networks for parallel and distributed computation, are suitable to develop simple and efficient algorithms with low communication costs. The wide applications of linear arrays and rings motivate us to investigate path and cycle embedding in networks. Some of previous researches on path or cycle embedding focused on finding longest paths or cycles (i.e., the Hamiltonian problem, in terms of graph theory). Some others focused on finding cycles of all possible lengths (i.e., the pancycle problem, in terms of graph theory).ince node faults and/or link faults may occur to networks, it is significant to consider faulty networks. Fault tolerance ability is an important consideration for interconnection network topology. That is, the network is still functional when some node faults and/or link faults occur. Among them, two fault models were adopted; one is the random fault model, and the other is the conditional fault model. The random fault model assumed that the faults might occur everywhere without any restriction, whereas the conditional fault model assumed that the distribution of faults must satisfy some properties. It is more difficult to solve problems under the conditional fault model than the random fault model.n this dissertation, we investigate fault-free path/cycle embedding problems with edge faults on three instances of Cayley graphs: star graphs, alternating group graphs, and pancake graphs. If the random fault model is adopted, we show that an n-dimensional alternating group graph is (2n−6)-edge-fault-tolerant pancyclic. This result is optimal with respect to the number of edge faults tolerated.n the other hand, under the conditional fault model and with the assumption of at least two non-faulty links incident to each node, we show that an n-dimensional star graph is (2n−7)-edge-fault-tolerant strongly Hamiltonian laceable and (n−4)-edge-fault-tolerant hyper Hamiltonian laceable, an n-dimensional alternating group graph is (4n−13)-edge-fault-tolerant Hamiltonian and (2n−7)-edge-fault-tolerant Hamiltonian connected, and an n-dimensional pancake graph is (2n−7)-edge-fault-tolerant Hamiltonian and (n−4)-edge-fault-tolerant Hamiltonian connected. The results on star graphs and alternating group graphs are optimal with respect to the number of edge faults tolerated. We also verify that the assumption is meaningful in practical by evaluating its probability of occurrence, which is very close to 1, even if n is small.
Subjects
star graph
alternating group graph
pancake graph
Cayley graph
embedding
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-D90922007-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):230b707acee80650c033758b8e8df4ca