-
Views
-
Cite
Cite
Jinn-Shyong Yang, Sih-Syuan Luo, Jou-Ming Chang, Pruning Longer Branches of Independent Spanning Trees on Folded Hyper-Stars, The Computer Journal, Volume 58, Issue 11, November 2015, Pages 2972–2981, https://doi.org/10.1093/comjnl/bxv029
Close - Share Icon Share
Abstract
Hypercubes and star graphs are widespread topologies of interconnection networks. The class of hyper-stars was introduced as a new type of interconnection network to compete with both hypercubes and star graphs, and the class of folded hyper-stars is a strengthened variation of hyper-stars with additional links to connect nodes with complemented 0/1-strings. Constructing independent spanning trees (ISTs) has numerous applications in networks such as fault-tolerant broadcasting and secure message distribution. Recently, Yang and Chang [IST on folded hyper-stars, Networks 56 (2010), 272–281] proposed an algorithm to construct |$k+1$| ISTs on folded hyper-star |$FHS(2k,k)$|. For |$k\geqslant 4$|, their constructions include |$k$| ISTs with a height |$2k-2$| and the other one with a height |$k+1$|. In this paper, we refine their constructed rules on |$FHS(2k,k)$| for |$k\geqslant 3$| and provide a set of constructions including |$k$| ISTs with a height |$k+2$| and the other one with a height |$k+1$|. As a by-product, we obtain an improvement on the upper bound of the fault diameter (respectively, the wide diameter) of |$FHS(2k,k)$|.
