Parallel Construction of Independent Spanning Trees on Enhanced Hypercubes.

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance, bandwidth and security. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on enhanced hypercubes Qn,k<alternatives> <inline-graphic xlink:type="simple" xlink:href="chang-ieq1-2367498.gif"/></alternatives>, which contain folded hypercubes as a subclass. Moreover, we show that these ISTs are near optimal for heights and path lengths. Let D(Qn,k)<alternatives><inline-graphic xlink:type="simple" xlink:href="chang-ieq2-2367498.gif"/></alternatives> denote the diameter of Qn,k<alternatives> <inline-graphic xlink:type="simple" xlink:href="chang-ieq3-2367498.gif"/></alternatives>. If n-k<alternatives><inline-graphic xlink:type="simple" xlink:href="chang-ieq4-2367498.gif"/></alternatives> is odd or n-k\in \lbrace 2,n\rbrace<alternatives> <inline-graphic xlink:type="simple" xlink:href="chang-ieq5-2367498.gif"/></alternatives>, we show that all the heights of ISTs are equal to D(Qn,k)+1<alternatives> <inline-graphic xlink:type="simple" xlink:href="chang-ieq6-2367498.gif"/></alternatives>, and thus are optimal. Otherwise, we show that each path from a node to the root in a spanning tree has length at most D(Qn,k)+2<alternatives><inline-graphic xlink:type="simple" xlink:href="chang-ieq7-2367498.gif"/></alternatives> . In particular, no more than 2.15 percent of nodes have the maximum path length. As a by-product, we improve the upper bound of wide diameter (respectively, fault diameter) of Qn,k <alternatives><inline-graphic xlink:type="simple" xlink:href="chang-ieq8-2367498.gif"/></alternatives> from these path lengths. [ABSTRACT FROM PUBLISHER]