期刊
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
卷 16, 期 9, 页码 853-865出版社
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2005.109
关键词
WK-recursive; embedding; Hamiltonian-connected; interconnection network; fault-tolerant embedding; Hamiltonian cycle
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 >= 1. In this paper, we first show that K(d, t) is Hamiltonian-connected, where d >= 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 >= 4. Since the connectivity of K(d, t) is d - 1, the result is optimal.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据