Construction of vertex-disjoint paths in alternating group networks |
| |
Authors: | Shuming Zhou Wenjun Xiao Behrooz Parhami |
| |
Affiliation: | 1.Key Laboratory of Network Security and Cryptology,Fujian Normal University,Fuzhou,People’s Republic of China;2.College of Mathematics and Computer Science,Fujian Normal University,Fuzhou,People’s Republic of China;3.Dept. Computer Science,South China University of Technology,Guangzhou,People’s Republic of China;4.Dept. Electrical and Computer Engineering,University of California,Santa Barbara,USA |
| |
Abstract: | The existence of parallel node-disjoint paths between any pair of nodes is a desirable property of interconnection networks, because such paths allow tolerance to node and/or link failures along some of the paths, without causing disconnection. Additionally, node-disjoint paths support high-throughput communication via the concurrent transmission of parts of a message. We characterize maximum-sized families of parallel paths between any two nodes of alternating group networks. More specifically, we establish that in a given alternating group network AN n , there exist n−1 parallel paths (the maximum possible, given the node degree of n−1) between any pair of nodes. Furthermore, we demonstrate that these parallel paths are optimal or near-optimal, in the sense of their lengths exceeding the internode distance by no more than four. We also show that the wide diameter of AN n is at most one unit greater than the known lower bound D+1, where D is the network diameter. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|