About this Computer Science article
Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes by Ruo-Wei Hung is a Computer Science article available to read on EtoBox.
The n-dimensional hypercube network Q n is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQ n , an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Q n . One advantage of LTQ n is that the diameter is only about half of the diameter of Q n . Recently, some interesting properties of LTQ n have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. The existence of two edge-disjoint Hamiltonian cycles in locally twisted cubes has remained unknown. In this paper, we prove that the locally twisted cube LTQ n with n ⩾ 4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2 n )-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQ n with n ⩾ 4, where LTQ n contains 2 n nodes and n2 n-1 edges.
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Ruo-Wei Hung
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)
- Published
- 2011
- Language
- EN
- Field
- Computer Science (Physical Sciences)