Software Engineering Commons^™

A Greedy Hypercube-Labeling Algorithm, D. Bhagavathi, C. E. Grosch, S. Olariu

Computer Science Faculty Publications

Due to its attractive topological properties, the hypercube multiprocessor has emerged as one of the architectures of choice when it comes to implementing a large number of computational problems. In many such applications, Gray-code labelings of the hypercube are a crucial prerequisite for obtaining efficient algorithms. We propose a greedy algorithm that, given an n-dimensional hypercube H with N=2² nodes, returns a Gray-code labeling of H, that is, a labeling of the nodes with binary strings of length n such that two nodes are neighbors in the hypercube if, and only if, their labels differ in exactly …