The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks
Yicheng Yang, Shih-Shun Kao, Ralf Klasing, Sun‐Yuan Hsieh, Hsin-Hung Chou, Jou–Ming Chang · IEEE Access · 2021
A set of the spanning trees in a graph$G$is called independent spanning trees if they have a common root$r$and for each vertex$v\in V(G)\setminus \{r\}$, the paths from$v$to$r$in any two trees are directed edge-disjoint and internally vertex-disjoint. The construction of independent spanning trees has many practical applications in reliable communication networks, such as fault-tolerant transmission and secure message distribution. A burnt pancake network$BP_{n}$is a kind of Cayley graph, which has been proposed as the topology of an interconnection network. In this paper, we provide a two stages construction scheme that can be used to construct a maximal number of independent spanning trees on a burnt pancake network in$O(N\times n)$time, where$N$is the number of nodes of$BP_{n}$and$n$is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees.