Embedding cycles and meshes onto incomplete hypercubes

An incomplete hypercube is a generalization of the hypercube in the sense t hat the number of nodes can be an arbitrary integer number. Moreover, we ca n enlarge its system size without reconfiguring the links. In this paper, w e study the incomplete hypercube's ability to execute parallel algorithms u sing embedding technique. Since many algorithms have been proposed for line ar arrays, cycles and meshes, the issues of embedding these interconnection networks are addressed. On the other hand, a multiprogramming system may o nly allocate part of the whole system for a task. Hence, we are motivated t o study the problem of how to embed these interconnection networks of an ar bitrary size into the incomplete hypercubes. For these embedding issues, we have proposed algorithms to enumerate these interconnection networks on th e incomplete hypercubes optimally and definitely, except only to prove the existence of these optimal embeddings.