Fault-tolerant routing in circulant networks and cycle prefix networks |
| |
Authors: | Sheng-Chyang Liaw Gerald J Chang Feng Cao D Frank Hsu |
| |
Institution: | (1) Department of Applied Mathematics, National Chiao Tung University, 30050 Hsinchu, Taiwan;(2) Department of Computer Science, University of Minnesota, 55455 Minneapolis, MN, USA;(3) Department of Computer and Information Science, Fordham University, LL813, 113 West 60th Street, 10023 New York, NY, USA |
| |
Abstract: | Reliability and efficiency are important criteria in the design of interconnection networks. Connectivity is a widely used measurement for network fault-tolerance capacities, while diameter determines routing efficiency along individual paths. In practice, we are interested in high-connectivity, small-diameter networks. Recently, Hsu introduced the notion ofw-wide diameter, which unifies diameter and connectivity. This paper investigates thew-wide diameterd
w
(G) and two related parameters:w-fault diameterD
w
(G) andw-Rabin numberr
w
(G). In particular, we determined
w
(G) andD
w
(G) for 2wK(G) andG is a circulant digraphG(d
n
; 1,d,...,d
n–1) or a cycle prefix digraph.Supported in part by the National Science Council under grant NSC86-2115-M009-002. |
| |
Keywords: | 05C12 05C40 |
本文献已被 SpringerLink 等数据库收录! |
|