TY - JOUR
T1 - Efficient embeddings of trees in hypercubes
AU - Bhatt, Sandeep N.
AU - Chung, Fan R.K.
AU - Leighton, F. Thomson
AU - Rosenberg, Arnold L.
PY - 1992
Y1 - 1992
N2 - The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded degree graph with an O(1)-separator can be embedded in a hypercube of the same size with dilation and congestion both O(1). It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.
AB - The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded degree graph with an O(1)-separator can be embedded in a hypercube of the same size with dilation and congestion both O(1). It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.
UR - http://www.scopus.com/inward/record.url?scp=0026818855&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026818855&partnerID=8YFLogxK
U2 - 10.1137/0221012
DO - 10.1137/0221012
M3 - Article
AN - SCOPUS:0026818855
SN - 0097-5397
VL - 21
SP - 161
EP - 162
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 1
ER -