| Autor: |
Yi-Cheng Yang, Shih-Shun Kao, Ralf Klasing, Sun-Yuan Hsieh, Hsin-Hung Chou, Jou-Ming Chang |
| Jazyk: |
angličtina |
| Rok vydání: |
2021 |
| Předmět: |
|
| Zdroj: |
IEEE Access, Vol 9, Pp 16679-16691 (2021) |
| Druh dokumentu: |
article |
| ISSN: |
2169-3536 |
| DOI: |
10.1109/ACCESS.2021.3049290 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
