Parallel Construction of Independent Spanning Trees on Folded Crossed Cubes
Huanwen Zhang, Yan Wang, Jianxi Fan, Ruyan Guo · 2021
Independent spanning trees (ISTs) play an important role in secure message distribution, bandwidth as well as fault-tolerant broadcasting. Thus the construction of ISTs on many classes of graphs has been investigated. The n-dimensional folded crossed cube FCQnis a strengthened variation of the n-dimensional crossed cube CQn, which is obtained from CQnby adding edges between any pair of vertices with furthest Hamming distance. In this paper, we study the existence and parallel construction of ISTs on FCQn. We first present the definition of Flag-Mapping and propose an algorithm to obtain the Flag-Mapping of each vertex on n +1 spanning trees of FCQn. Then based on the outputs of above algorithm, we propose a fully parallelized algorithm with the time complexity O(n) by using N processors to construct n +1 ISTs on FCQn, where n ≥ 1 and N =2n, and present the corresponding simulation experiments to verify its validity.