Constructing independent spanning trees with height n on the n-dimensional crossed cube

摘要

Independent spanning trees (ISTs) on networks have applications in reliable broadcasting, reliable communication protocols, secure message distribution. Towards the ISTs on crossed cubes, although several results have been obtained, the maximum height of the ISTs on the n-dimensional crossed cube CQ(n) is no less than n + 1 for n = 3. So we have the question whether there exist multiple ISTs with height lower than n + 1 on CQ(n). In this paper, firstly, we present the construction of n - 2 ISTs rooted at node 0 on CQ(n), the maximum height of which is no more than n for n = 4. A parallel algorithm with the time complexity O(N) is also presented, where N = 2(n). Secondly, we present a binary XOR operation to transform the above n - 2 ISTs into the n - 2 ISTs rooted at any node that is similar to 0 on CQ(n). Thirdly, we revise the recursive algorithm CIST from Cheng et al. (2013) to construct n - 2 ISTs rooted at any node on CQ(n) with the maximal height n, where the time complexity is O(N log(2) N). We have also extended the efficient parallel method to locally twisted cubes. (C) 2018 Elsevier B.V. All rights reserved.