CONNECTIVITY OF CARTESIAN PRODUCT DIGRAPHS AND FAULT-TOLERANT ROUTINGS OF GENERALIZED HYPERCUBE

ＣＯＮＮＥＣＴＩＶＩＴＹＯＦＣＡＲＴＥＳＩＡＮＰＲＯＤＵＣＴＤＩＧＲＡＰＨＳＡＮＤＦＡＵＬＴ┐ＴＯＬＥＲＡＮＴＲＯＵＴＩＮＧＳＯＦＧＥＮＥＲＡＬＩＺＥＤＨＹＰＥＲＣＵＢＥＸＵＪＵＮＭＩＮＧＡｂｓｔｒａｃｔ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｐｒｏｂｌｅｍ...

Connectivity of cartesian product digraphs and fault-tolerant routings of generalized hypercube

In this paper,the problem of fault-tolerant routings in fault-tolerant networks is considered. A routing in a network assigns to each ordered pair of nodes a fixed path. All commu-nication among nodes must go on this routing. When either a node or a link in a fault-tolerant network fails, the communication from one node to another using this faulty element must be sent via one or more intermediate nodes along a sequence of paths determined by this routing. An important and practical problem is how to choose a routing in the network such that inter-mediate nodes to ensure communication are small for any fault-set. Let C _d be a directed cycle of order d. In this paper. The author first discusses connectivity of Cartesian product digraphs, then proves that the Cartesian product digraph Cd₁ ×Cd₂×... ×Cd_n(d₁≥2.1≤n) has a rout-ing such that at most one intermediate node is needed to ensure transmission of messages among all non-faulty nodes so long as the number of faults is less than n. This is a generalization of Dolev et al’s result for the n-dimensional cube. Supported partly by the National Natural Science Foundation of China (19671057).