Broadcasting and Embedding Algorithms for a Half Hypercube Interconnection Network

The half hypercube interconnection network, has been proposed as a new variation of the hypercube, reducing its degree by approximately half with the same number of nodes as an n-dimensional hypercube, Q _n . This paper proposes an algorithm for one-to-many broadcasting in an n-dimensional half hypercube, HH _n , and examines the embedding between hypercube and half hypercube graphs. The results show that the one-to-many broadcasting time of the HH _n can be accomplished in n + 1 when n is an even number and in \( 2 \times \lceil n/ 2\rceil \) when n is an odd number. The embedding of HH _n into Q _n can be simulated in constant time O(n) and the embedding of Q _n into HH _n in constant time O(1).