Incomplete hypercubes

Since a k-dimensional hypercube has 2^k vertices, these systems are restricted to having exactly 2^k computing nodes. Because system sizes must be a power of two, there are large gaps in the sizes of systems that can be built with hypercubes. Routing and broadcast algorithms are presented for hypercubes that are missing certain of their nodes, called incomplete hypercubes. Unlike hypercubes, incomplete hypercubes can be used to interconnect systems with any number of processors. The routing and broadcast algorithms for incomplete hypercubes are shown also to be simple and deadlock-free