Independent spanning trees on WK-recursive networks and WK-recursive pyramids

The use of independent spanning trees (ISTs) has scientific applications in fault-tolerant requirement in network protocols and secure message distributions. Most of the designs of ISTs are for those interconnection networks with vertex symmetric property, implying that one can find ISTs rooted on a designated vertex, and, by the vertex symmetry property of the given network, hence have solved the ISTs problem on any arbitrary vertex. The existence of asymmetry makes the ISTs problem even harder than its symmetric counterpart. In this paper, we propose two linear time algorithms that solved ISTs rooted at an arbitrary vertex of WK-recursive networks and WK-recursive pyramids separately. The performance of the proposed algorithms is evaluated both, analytically and experimentally, in terms of tree heights and average distances.

Automated summary

This paper proposes two linear time algorithms to solve the ISTs rooted at an arbitrary vertex for WK-recursive networks and WK-recursive pyramids separately. The performance of the algorithms is evaluated through analytical and experimental analysis of tree heights and average distances.