Construction of optimal independent spanning trees on folded hypercubes

The n-dimensional folded hypercube FQ(n) is an important variant of the n-dimensional hypercube Q(n), which is obtained from Q(n), by adding an edge between any pair of vertices with complementary addresses. The diameter of FQ(n) is [n/2], about half the diameter of Q(n). A set of k(>= 2) spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, with one path in each spanning tree, are internally disjoint. By using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Recently, Yang et al. proposed an algorithm, which can be parallelized, for constructing n + 1 ISTs on FQ(n) with the height of each spanning tree being n. In this paper, we propose an algorithm for constructing n + 1 optimal ISTs on FQ(n) in the sense that there is a shortest path between the only child of the root rand any other vertex in each spanning tree (therefore, the height of each spanning tree is [n/2] + 1). Moreover, the algorithm runs in time O((n + 1)N) and can be parallelized to run by using N= 2(n) processors on FQ(n) in time O(n). (C) 2013 Elsevier Inc. All rights reserved.