Xiaorui Li ; Baolei Cheng ; Jianxi Fan ; Yan Wang ; Dajin Wang - On Completely Edge-Independent Spanning Trees in Locally Twisted Cubes

fi:12785 - Fundamenta Informaticae, May 14, 2025, Volume 193
On Completely Edge-Independent Spanning Trees in Locally Twisted CubesArticle

Authors: Xiaorui Li ; Baolei Cheng ; Jianxi Fan ; Yan Wang ; Dajin Wang

    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.


    Volume: Volume 193
    Published on: May 14, 2025
    Accepted on: November 12, 2024
    Submitted on: January 5, 2024
    Keywords: Computer Science - Distributed, Parallel, and Cluster Computing,Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 19 times.
    This article's PDF has been downloaded 5 times.