TY - JOUR
T1 - Fault-tolerant embedding of complete binary trees in locally twisted cubes
AU - Liu, Zhao
AU - Fan, Jianxi
AU - Zhou, Jingya
AU - Cheng, Baolei
AU - Jia, Xiaohua
PY - 2017/3/1
Y1 - 2017/3/1
N2 - The complete binary tree is an important network structure for parallel and distributed computing, which has many nice properties and is often used to be embedded into other interconnection architectures. The locally twisted cube LTQn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. The main results obtained in this paper are: (1) The complete binary tree CBTn rooted at an arbitrary vertex of LTQn can be embedded with dilation 2 and congestion 1 into LTQn. (2) When there exists only one faulty node in LTQn, both the dilation and congestion will become 2 after reconfiguring CBTn. (3) When there exist two faulty nodes in LTQn, then both the dilation and congestion will become 3 after reconfiguring CBTn. (4) For any faulty set F of LTQn with 2n−1, both the dilation and congestion will become 3 after reconfiguring CBTn under certain constraints.
AB - The complete binary tree is an important network structure for parallel and distributed computing, which has many nice properties and is often used to be embedded into other interconnection architectures. The locally twisted cube LTQn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. The main results obtained in this paper are: (1) The complete binary tree CBTn rooted at an arbitrary vertex of LTQn can be embedded with dilation 2 and congestion 1 into LTQn. (2) When there exists only one faulty node in LTQn, both the dilation and congestion will become 2 after reconfiguring CBTn. (3) When there exist two faulty nodes in LTQn, then both the dilation and congestion will become 3 after reconfiguring CBTn. (4) For any faulty set F of LTQn with 2n−1, both the dilation and congestion will become 3 after reconfiguring CBTn under certain constraints.
KW - Complete binary tree
KW - Congestion
KW - Dilation
KW - Embedding
KW - Fault-tolerance
KW - Interconnection architecture
KW - Locally twisted cube
UR - http://www.scopus.com/inward/record.url?scp=85002773588&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85002773588&origin=recordpage
U2 - 10.1016/j.jpdc.2016.11.005
DO - 10.1016/j.jpdc.2016.11.005
M3 - 21_Publication in refereed journal
VL - 101
SP - 69
EP - 78
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
SN - 0743-7315
ER -