Research On Embedding Of Complete Binary Tree In Hypercube Variant Network

In recent years,parallel computing has played an increasingly important role in scientific research,education,biology,meteorology and other fields.Multiprocessor interconnected networks determine the performance of parallel computing,so researching interconnected networks is of great significance.The interconnection network can be represented by a graph,where the vertices represent processors,and the edges represent physical links between processors.The performance of graph embedding is usually characterized by parameters such as degree of dilation,congestion,expansion,and load,which is also an important indicator to measure the quality of the interconnected network.The CBT_n has superior performance and wide application.So far,many achievements have been made in the research of embedding CBT_n in mesh,grid,star graph,butterfly network and others,but few research results in hypercube variant networks.This paper studies the embedding of CBT_n on AQ_n and MQ_n.By using a computer program to search the network in the low-dimensional,and the mathematical induction of the network with its own properties in the case of high dimension,the results are as follows:(1)We prove that CBT_n with 2~n vertices can be embedded into AQ_n with dilation 1,load1,congestion 1,and expansion 1.(2)We prove that when any vertex fails on AQ_n,CBT_n can be dynamically reconstructed with dillation 2 and congestion 2.(3)We prove that when any two vertices fail on AQ_n,CBT_n can be dynamically reconst-ructed with dilation 3 and congestion 2.(4)We prove that when the number of faulty vertices exceeds two,under the restricted conditions,CBT_n can be dynamically reconstructed with dilation 3 and congestion 2.(5)We prove that the complete binary tree can be embedded into MQ_n with dilation 1,load 1,congestion 1 and expansion 1.