English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, two spanning trees <inline-formula> <tex-math notation="LaTeX">$T_{1}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T_{2}$ </tex-math></inline-formula> are rooted at the same vertex <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>. If, for every <inline-formula> <tex-math notation="LaTeX">$v \in V(G)$ </tex-math></inline-formula>, the paths from <inline-formula> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula> to the root <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> in <inline-formula> <tex-math notation="LaTeX">$T_{1}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T_{2}$ </tex-math></inline-formula> 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 (<inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>,<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>)-star graphs <inline-formula> <tex-math notation="LaTeX">$S_{n,k}$ </tex-math></inline-formula> constitute a generalized version of the star network. The method of constructing ISTs in (<inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>,<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>)-star graphs remains unknown. In this paper, we propose one recursive algorithm and one parallel algorithm for constructing ISTs on (<inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>,<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>)-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 <inline-formula> <tex-math notation="LaTeX">$S_{n,k}$ </tex-math></inline-formula> is <inline-formula> <tex-math notation="LaTeX">$O\left({n\times \frac {n!}{(n-k)!}}\right)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\frac {n!}{(n-k)!}$ </tex-math></inline-formula> is the number of nodes of <inline-formula> <tex-math notation="LaTeX">$S_{n,k}$ </tex-math></inline-formula>. The time complexity of the parallel algorithm can be reduced to <inline-formula> <tex-math notation="LaTeX">$O\left({\frac {n!}{(n-k)!}}\right)$ </tex-math></inline-formula> if the system has <inline-formula> <tex-math notation="LaTeX">$n-1$ </tex-math></inline-formula> processors computing in parallel. Both algorithms are correct with the stated time complexity values; the parallel algorithm is more efficient than the recursive algorithm.

Two Algorithms for Constructing Independent Spanning Trees in (n,k)-Star Graphs