Incomplete crossed hypercubes

In this paper, a new interconnection network called the incomplete crossed hypercube is proposed for connecting processors of parallel computing systems. The incomplete crossed hypercube architecture denoted by CI (n-m) (n) is made by combining two complete crossed hypercubes CQ (n) and CQ (n-m) for 1a parts per thousand currency signma parts per thousand currency signn. Several topological properties of CI (n-m) (n) are analyzed. In particular, accurate mean internode distance formulas of both CQ (n) and CI (n-m) (n) are given. Compared with the incomplete enhanced hypercube EI (n-m) (n) , CI (n-m) (n) has shorter mean internode distance for large n. An optimal routing algorithm for CI (n-m) (n) is also described which guarantees the generation of a shortest path from a node to another in CI (n-m) (n) .