OPTIMAL SIMULATIONS OF TREE MACHINES.

Sandeep Bhatt, Fan Chung, Tom Leighton, Arnold Rosenberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

120 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
Pages274-282
Number of pages9
DOIs
StatePublished - 1986

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Fingerprint

Dive into the research topics of 'OPTIMAL SIMULATIONS OF TREE MACHINES.'. Together they form a unique fingerprint.

Cite this