Can I read Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes on EtoBox?

Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes by Ruo-Wei Hung is a Computer Science article available to read on EtoBox.

What is Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes about?

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.

Who reads Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes?

Author

Ruo-Wei Hung

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2011

Language

EN

Field

Computer Science (Physical Sciences)