首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Hamiltonicity of the WK-recursive network with and without faulty nodes
【24h】

Hamiltonicity of the WK-recursive network with and without faulty nodes

机译:有无故障节点的WK递归网络的哈密顿性

获取原文
获取原文并翻译 | 示例

摘要

Recently, the WK-recursive network has received much attention due to its many favorable properties such as a high degree of scalability. By K(d,t), we denote the WK-recursive network of level t, each of whose basic modules is a d-node complete graph, where d>1 and t/spl ges/1. In this paper, we first show that K(d,t) is Hamiltonian-connected, where d/spl ges/4. A network is Hamiltonian-connected if it contains a Hamiltonian path between every two distinct nodes. In other words, a Hamiltonian-connected network can embed the longest linear array between any two distinct nodes with dilation, congestion, load, and expansion all equal to one. Then, we construct fault-free Hamiltonian cycles in K(d,t) with at most d-3 faulty nodes, where d/spl ges/4. Since the connectivity of K(d,t) is d-1, the result is optimal.
机译:最近,WK递归网络由于其许多有利的特性(例如高度可伸缩性)而受到了广泛的关注。用K(d,t)表示级别t的WK递归网络,其每个基本模块都是d节点完整图,其中d> 1且t / spl ges / 1。在本文中,我们首先证明K(d,t)是哈密顿连通的,其中d / spl ges / 4。如果网络在每两个不同的节点之间包含哈密顿路径,则该网络为哈密顿连接。换句话说,连接哈密顿量的网络可以在任意两个不同的节点之间嵌入最长的线性数组,它们的膨胀,拥塞,负载和扩展都等于1。然后,我们在K(d,t)中构造最多无d-3个故障节点的无故障哈密顿环,其中d / spl ges / 4。由于K(d,t)的连通性为d-1,因此结果最佳。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号