Efficient Embeddings of Trees in Hypercubes

DOI10.1137/0221012zbMath0743.68037OpenAlexW2162335953MaRDI QIDQ3990107

Arnold L. Rosenberg, Sandeep N. Bhatt, Frank Thompson Leighton, Fan R. K. Chung

Publication date: 28 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221012

zbMATH Keywords

expansiondilationtree decompositioncongestionbinary treesgraph embeddingboolean hypercube

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

A probably optimal embedding of hyper-rings in hypercubes ⋮ An approach to emulating separable graphs ⋮ A new combinatorial approach to optimal embeddings of rectangles ⋮ Embedding trees in recursive circulants ⋮ Compressing grids into small hypercubes ⋮ Embedding ladders and caterpillars into the hypercube ⋮ On some similarity of finite sets (and what we can say today about certain old problem) ⋮ Hypercube embedding heuristics: An evaluation ⋮ Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees ⋮ Product-shuffle networks: Toward reconciling shuffles and butterflies ⋮ Wirelength of hypercubes into certain trees ⋮ Unnamed Item ⋮ Embedding multidimensional grids into optimal hypercubes ⋮ Unnamed Item ⋮ Embedding meshes in hypercubes with edge faults ⋮ Recursive circulants and their embeddings among hypercubes ⋮ A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion

This page was built for publication: Efficient Embeddings of Trees in Hypercubes