A Parallel Algorithm for Constructing Two Edge-disjoint Hamiltonian Cycles in Locally Twisted Cubes
Shun‐Yu Li, Jou–Ming Chang, Kung-Jui Pai · 2020
The locally twisted cube LTQnis a variation of the hypercube Qn, and the diameter of LTQnis only about half of the diameter of Qn. For interconnection networks, some efficient communication algorithms can be designed based on the ring structure. In addition, two edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity for the interconnection network. Hung [Theoretical Computer Science 412, 4747-4753, 2011] designed an O(n2n) time algorithm to construct two edge-disjoint Hamiltonian cycles in LTQn. In this paper, we provide parallel algorithms for each vertex in LTQnto determine which two edges were adopted in the first or second Hamiltonian cycles, respectively. By connecting these edges, we can construct two edge-disjoint Hamiltonian cycles in LTQnwhere n ≥ 4.