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 ⁿ is made by combining two complete crossed hypercubes CQ _n and CQ _n−m for 1≤m≤n. Several topological properties of CI _n−m ⁿ are analyzed. In particular, accurate mean internode distance formulas of both CQ _n and CI _n−m ⁿ are given. Compared with the incomplete enhanced hypercube EI _n−m ⁿ , CI _n−m ⁿ has shorter mean internode distance for large n. An optimal routing algorithm for CI _n−m ⁿ is also described which guarantees the generation of a shortest path from a node to another in CI _n−m ⁿ .