TY - GEN
T1 - OPTIMAL SIMULATIONS OF TREE MACHINES.
AU - Bhatt, Sandeep
AU - Chung, Fan
AU - Leighton, Tom
AU - Rosenberg, Arnold
PY - 1986
Y1 - 1986
N2 - The authors investigate simulations of tree machines, motivated by the fact that divide-and-conquer algorithms are programmed naturally on trees. Their first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. The authors also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks.
AB - The authors investigate simulations of tree machines, motivated by the fact that divide-and-conquer algorithms are programmed naturally on trees. Their first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. The authors also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks.
UR - http://www.scopus.com/inward/record.url?scp=0022874323&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022874323&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1986.38
DO - 10.1109/sfcs.1986.38
M3 - Conference contribution
AN - SCOPUS:0022874323
SN - 0818607408
SN - 9780818607400
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 274
EP - 282
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
ER -