Efficient embeddings of trees in hypercubes

Sandeep N. Bhatt, Fan R.K. Chung, F. Thomson Leighton, Arnold L. Rosenberg

Research output: Contribution to journalArticlepeer-review

67 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)161-162
Number of pages2
JournalSIAM Journal on Computing
Volume21
Issue number1
DOIs
StatePublished - 1992

Fingerprint

Dive into the research topics of 'Efficient embeddings of trees in hypercubes'. Together they form a unique fingerprint.

Cite this