Generalized hypercubes (GHC) consist of n m

× n m-1

× . . . n 1

nodes represented as (i m

, i m-

1

, . . . . , i 1

), 0 £ i k £ n k

- 1.

Two nodes (i m

, i m-1

, . . ., i 1

) and (j m

, j m-1

, . . . j 1

) in a GHC are connected iff there exists exactly one l (1

if k ¹ l and i k

= j k

if k = l. The following is an example of a 4 × 3 × 2 GHC.

(a) Provide a general shortest-path routing algorithm for GHCs.

(b) Find the number of node-disjoint shortest paths between two nodes in an n m × n m-1 × . . . × n 1 GHC.

Transcribed Image Text:

020 010 021 121 221 100 200 300 000 321 311 301