Complete binary trees embeddings in Möbius cubes

•We propose an approach to embed the complete binary tree into the n-dimensional Möbius cube Mn.•We prove that the complete binary tree with 2n−1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.•The research result in this paper demonstrates that emb...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2016-03, Vol.82 (2), p.260-281
Main Authors: Liu, Zhao, Fan, Jianxi, Jia, Xiaohua
Format: Article
Language:English
Subjects:
Complete binary tree
Congestion
Dilation
Expansion
Interconnection architecture
Load
Möbius cube
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We propose an approach to embed the complete binary tree into the n-dimensional Möbius cube Mn.•We prove that the complete binary tree with 2n−1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.•The research result in this paper demonstrates that embeddability of the complete binary tree in the n-dimensional Möbius cube is superior to that in the n-dimensional hypercube. The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The Möbius cube Mn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. In this paper, we prove that the complete binary tree with 2n−1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2015.09.004