Fault-tolerant embedding of complete binary trees in locally twisted cubes

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

11 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)69-78
Journal / PublicationJournal of Parallel and Distributed Computing
Publication statusPublished - 1 Mar 2017


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.

Research Area(s)

  • Complete binary tree, Congestion, Dilation, Embedding, Fault-tolerance, Interconnection architecture, Locally twisted cube