One-to-one communication in twisted cubes under
restricted connectivity |
| |
Authors: | Jianxi FAN Shukui ZHANG Wujun ZHOU Baolei CHENG Kenli LI |
| |
Affiliation: | 1.School of Computer Science
and Technology, Soochow University, Suzhou 215006, China; 2.School of Computer and
Communication, Hunan University, Changsha 410082, China; |
| |
Abstract: | The dimensions of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all positive integers. Then, we introduce the concept of the restricted faulty set into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQn has at least one fault-free neighbor, its restricted connectivity is 2n − 2, which is almost twice as that of TQn under the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we provide an O(NlogN) fault-free unicast algorithm and simulations result of the expected length of the fault-free path obtained by our algorithm, where N denotes the node number of TQn. Finally, we propose a polynomial algorithm to check whether the faulty node set satisfies the condition that each node of the n-dimensional twisted cube TQn has at least one fault-free neighbor. |
| |
Keywords: | connectivity set of restricted faulty nodes unicast fault-free path twisted cube |
|
| 点击此处可从《Frontiers of Computer Science》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Computer Science》下载全文 |
|