Fault-free longest paths in star networks with conditional link faults
Fault-free longest paths in star networks with conditional link faults
复制标题
DOI：
10.1016/j.tcs.2008.11.012
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Ping-Ying Tsai;Jung-Sheng Fu;Gen-Huey Chen
中科院分区：
文献类型：
--
作者：
Ping-Ying Tsai;Jung-Sheng Fu;Gen-Huey Chen
星星网络属于Cayley图类，是并行和分布式计算中最常用的互连网络之一。本文采用条件故障模型，假设每个节点与两个或多个无故障链路关联，证明了一个n维星星网络可以容忍多达2n−7个链路故障，并且是强（无故障）Hamilton网，其中n≥4.换句话说，我们可以嵌入一个长度为n的无故障线性阵列！−1（n！-2）在具有多达2n-7个链路故障的n维星星网络中，如果两个端节点属于不同的分集（相同的分集）。结果是最佳的链路故障容忍的数量。我们已经知道，在随机故障模型下，一个n维星星网络可以容忍多达n−3个故障链路，并且是强哈密顿可撕裂的，其中n≥3。
The star network, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. In this paper, adopting the conditional fault model in which each node is assumed to be incident with two or more fault-free links, we show that an n-dimensional star network can tolerate up to 2n−7 link faults, and be strongly (fault-free) Hamiltonian laceable, where n≥4. In other words, we can embed a fault-free linear array of length n!−1 (n!−2) in an n-dimensional star network with up to 2n−7 link faults, if the two end nodes belong to different partite sets (the same partite set). The result is optimal with respect to the number of link faults tolerated. It is already known that under the random fault model, an n-dimensional star network can tolerate up to n−3 faulty links and be strongly Hamiltonian laceable, for n≥3.