## Abstract

In a graph G, two spanning trees T_{1} and T_{2} are rooted at the same vertex r. If, for every v ∈ V(G), the paths from v to the root r in T_{1} and T_{2} are internally vertex-disjoint, they are called independent spanning trees (ISTs). ISTs can be applied in numerous fields, such as fault-tolerant broadcasting and secure message distribution. The (n,k)-star graphs S_{n,k} constitute a generalized version of the star network. The method of constructing ISTs in (n,k)-star graphs remains unknown. In this paper, we propose one recursive algorithm and one parallel algorithm for constructing ISTs on (n,k)-star graphs. The main ideas of the recursive algorithm are to use induction to change small trees into large trees, to use a modified breadth-first search (MBFS) traversal to create a frame for an IST, and to use a breadth-first search (BFS) traversal to connect the rest of nodes. The main ideas of the parallel algorithm are to create frames through MBFS traversals in parallel, and to use some specific rules to connect the rest of nodes in parallel. We also present validation proofs for both algorithms, and analyze the time complexities of both algorithms. The time complexity of the recursive algorithm in S_{n,k} is O(n × _{(}n_{−}^{n}^{!}_{k})_{!} ), where _{(}n_{−}^{n}^{!}_{k})_{!} is the number of nodes of S_{n,k}. The time complexity of the parallel algorithm can be reduced to O(_{(}n_{−}^{n}^{!}_{k})_{!} ) if the system has n − 1 processors computing in parallel. Both algorithms are correct with the stated time complexity values; the parallel algorithm is more efficient than the recursive algorithm.

Original language | English |
---|---|

Pages (from-to) | 175932-195947 |

Number of pages | 20016 |

Journal | IEEE Access |

Volume | 8 |

DOIs | |

Publication status | Published - 2020 |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Materials Science(all)
- Engineering(all)