Congestion and fault tolerance of binary tree embeddings on hypercube
Kemal Efe, Kumar Ramaiyer · 2002
An embedding of a binary tree on a hypercube utilizes at most three connections per embedded tree node. The authors show that the remaining connections can be profitably utilized to enhance various properties of embedding. These include (a) the ability for embedding large binary trees in smaller hypercubes by increasing the congestion of embedding uniformly across the nodes of the hypercube and (b) the ability to tolerate node failures in a way which requires minimum (and sometimes no) slowdown in executing binary tree algorithms. The methods described are quite general and can be extended to any embedding of a graph on hypercube.>