On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910108176351232 |
|---|---|
| author | Li, Xiaorui Cheng, Baolei Fan, Jianxi Wang, Yan Wang, Dajin |
| author_facet | Li, Xiaorui Cheng, Baolei Fan, Jianxi Wang, Yan Wang, Dajin |
| contents | A network can contain numerous spanning trees. If two spanning trees $T_i,T_j$ do not share any common edges, $T_i$ and $T_j$ are said to be pairwisely edge-disjoint. For spanning trees $T_1, T_2, ..., T_m$, if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct $\lfloor \frac{n}{2} \rfloor$ CEISTs in $LTQ_n$, the $n$-dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the $LTQ_n$ was simulated using $\lfloor\frac{n}{2}\rfloor$ CEISTs, and the performance compared with broadcasting using a single tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_01585 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes Li, Xiaorui Cheng, Baolei Fan, Jianxi Wang, Yan Wang, Dajin Distributed, Parallel, and Cluster Computing Discrete Mathematics A network can contain numerous spanning trees. If two spanning trees $T_i,T_j$ do not share any common edges, $T_i$ and $T_j$ are said to be pairwisely edge-disjoint. For spanning trees $T_1, T_2, ..., T_m$, if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct $\lfloor \frac{n}{2} \rfloor$ CEISTs in $LTQ_n$, the $n$-dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the $LTQ_n$ was simulated using $\lfloor\frac{n}{2}\rfloor$ CEISTs, and the performance compared with broadcasting using a single tree. |
| title | On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics |
| url | https://arxiv.org/abs/2401.01585 |