A GREEDY HYPERCUBE-LABELING ALGORITHM

Due to its attractive topological properties, the hypercube multiproce ssor has emerged as one of the architectures of choice when it comes t o implementing a large number of computational problems. In many such applications, Gray-code labelings of the hypercube are a crucial prere quisite for obtaining efficient algorithms. We propose a greedy algori thm that, given an n-dimensional hypercube H with N = 2(2) nodes, retu rns a Gray-code labeling of H, that is, a labeling of the nodes with b inary strings of length n such that two nodes are neighbors in the hyp ercube if, and only if, their labels differ in exactly one bit. Our al gorithm is conceptually very simple and runs in O(N log N) time being, therefore, optimal. As it turns out, with a few modifications our lab eling algorithm can be used to recognize hypercubes as well.