The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks
A set of the spanning trees in a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> is called independent spanning trees if they have a common root <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math>...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9314008/ |
| _version_ | 1811209820073623552 |
|---|---|
| author | Yi-Cheng Yang Shih-Shun Kao Ralf Klasing Sun-Yuan Hsieh Hsin-Hung Chou Jou-Ming Chang |
| author_facet | Yi-Cheng Yang Shih-Shun Kao Ralf Klasing Sun-Yuan Hsieh Hsin-Hung Chou Jou-Ming Chang |
| author_sort | Yi-Cheng Yang |
| collection | DOAJ |
| description | A set of the spanning trees in a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> is called independent spanning trees if they have a common root <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> and for each vertex <inline-formula> <tex-math notation="LaTeX">$v\in V(G)\setminus \{r\}$ </tex-math></inline-formula>, the paths from <inline-formula> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$BP_{n}$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$O(N\times n)$ </tex-math></inline-formula> time, where <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> is the number of nodes of <inline-formula> <tex-math notation="LaTeX">$BP_{n}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees. |
| first_indexed | 2024-04-12T04:45:24Z |
| format | Article |
| id | doaj.art-13180a7439f249ae8998ae6cf6bb3713 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T04:45:24Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-13180a7439f249ae8998ae6cf6bb37132022-12-22T03:47:30ZengIEEEIEEE Access2169-35362021-01-019166791669110.1109/ACCESS.2021.30492909314008The Construction of Multiple Independent Spanning Trees on Burnt Pancake NetworksYi-Cheng Yang0Shih-Shun Kao1https://orcid.org/0000-0001-7695-3535Ralf Klasing2Sun-Yuan Hsieh3https://orcid.org/0000-0003-4746-3179Hsin-Hung Chou4https://orcid.org/0000-0003-1627-9598Jou-Ming Chang5https://orcid.org/0000-0002-9542-7968Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, TaiwanDepartment of Computer Science and Information Engineering, National Cheng Kung University, Tainan, TaiwanCNRS, LaBRI, Université de Bordeaux, Talence cedex, FranceDepartment of Computer Science and Information Engineering, Institute of Medical Informatics, National Cheng Kung University, Tainan, TaiwanDepartment of Information Management, Chang Jung Christian University, Tainan, TaiwanInstitute of Information and Decision Sciences, National Taipei University of Business, Taipei, TaiwanA set of the spanning trees in a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> is called independent spanning trees if they have a common root <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> and for each vertex <inline-formula> <tex-math notation="LaTeX">$v\in V(G)\setminus \{r\}$ </tex-math></inline-formula>, the paths from <inline-formula> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$BP_{n}$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$O(N\times n)$ </tex-math></inline-formula> time, where <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> is the number of nodes of <inline-formula> <tex-math notation="LaTeX">$BP_{n}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees.https://ieeexplore.ieee.org/document/9314008/Independent spanning treesburnt pancake networkinterconnection networksfault-tolerant transmissionsecure message distribution |
| spellingShingle | Yi-Cheng Yang Shih-Shun Kao Ralf Klasing Sun-Yuan Hsieh Hsin-Hung Chou Jou-Ming Chang The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks IEEE Access Independent spanning trees burnt pancake network interconnection networks fault-tolerant transmission secure message distribution |
| title | The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks |
| title_full | The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks |
| title_fullStr | The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks |
| title_full_unstemmed | The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks |
| title_short | The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks |
| title_sort | construction of multiple independent spanning trees on burnt pancake networks |
| topic | Independent spanning trees burnt pancake network interconnection networks fault-tolerant transmission secure message distribution |
| url | https://ieeexplore.ieee.org/document/9314008/ |
| work_keys_str_mv | AT yichengyang theconstructionofmultipleindependentspanningtreesonburntpancakenetworks AT shihshunkao theconstructionofmultipleindependentspanningtreesonburntpancakenetworks AT ralfklasing theconstructionofmultipleindependentspanningtreesonburntpancakenetworks AT sunyuanhsieh theconstructionofmultipleindependentspanningtreesonburntpancakenetworks AT hsinhungchou theconstructionofmultipleindependentspanningtreesonburntpancakenetworks AT joumingchang theconstructionofmultipleindependentspanningtreesonburntpancakenetworks AT yichengyang constructionofmultipleindependentspanningtreesonburntpancakenetworks AT shihshunkao constructionofmultipleindependentspanningtreesonburntpancakenetworks AT ralfklasing constructionofmultipleindependentspanningtreesonburntpancakenetworks AT sunyuanhsieh constructionofmultipleindependentspanningtreesonburntpancakenetworks AT hsinhungchou constructionofmultipleindependentspanningtreesonburntpancakenetworks AT joumingchang constructionofmultipleindependentspanningtreesonburntpancakenetworks |