Efficient Embeddings of Trees in Hypercubes

DOI10.1137/0221012MaRDI QIDQ3990107zbMATH OpenOpenAlexFDO

Authors Sandeep Bhatt, Arnold L. Rosenberg, Fan Chung, F. Thomson Leighton

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

binary treesboolean hypercubecongestiondilationexpansiongraph embeddingtree decomposition

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4064517
• Embedding grids into hypercubes
• scientific article; zbMATH DE number 1769334
• Dense edge-disjoint embedding of complete binary trees in the hypercube
• Efficient embeddings of ternary trees into hypercubes.

Cited in

(38)

• Optimal one-page tree embeddings in linear time
• Optimal dynamic embedding of X-trees into arrays
• Product-shuffle networks: Toward reconciling shuffles and butterflies
• A probably optimal embedding of hyper-rings in hypercubes
• Embedding ladders and caterpillars into the hypercube
• Efficient embeddings of ternary trees into hypercubes.
• Recursive circulants and their embeddings among hypercubes
• On optimal embeddings and trees
• Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees
• Wirelength of hypercubes into certain trees
• A new combinatorial approach to optimal embeddings of rectangles
• Embedding trees in recursive circulants
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
• Embeddings Between Hypercubes and Hypertrees
• Towards optimal embedding of an arbitrary tree in a graceful tree
• scientific article; zbMATH DE number 3866594 (Why is no real title available?)
• scientific article; zbMATH DE number 4064517 (Why is no real title available?)
• Locality, Communication, and Interconnect Length in Multicomputers
• Embedding meshes in hypercubes with edge faults
• An approach to emulating separable graphs
• Compressing grids into small hypercubes
• scientific article; zbMATH DE number 1769334 (Why is no real title available?)
• Embedding graphs with bounded treewidth into optimal hypercubes
• Efficient Embeddings into Hypercube-like Topologies
• scientific article; zbMATH DE number 842025 (Why is no real title available?)
• A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube
• Efficient Schemes for Computing α-tree Representations
• scientific article; zbMATH DE number 7250384 (Why is no real title available?)
• A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES
• Embedding a subclass of trees into hypercubes
• On some similarity of finite sets (and what we can say today about certain old problem)
• Embeddings of hyper-rings in hypercubes
• Compact embedding of binary trees into hypercubes
• Hamiltonicity of random subgraphs of the hypercube
• Embedding multidimensional grids into optimal hypercubes
• Embeddings on a Boolean cube
• Hypercube embedding heuristics: An evaluation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990107)