Algorithmic Construction of Hamiltonian Cycles in OTIS-Networks

M. Hoseiny Farahabady and H. Sarbazi-Azad (Iran)


Interconnection networks, OTIS-Networks, Hamiltonian,Swapped Interconnection networks, embedding.


Recently, the OTIS-Network has received much attention due to its many favorable properties such as a high degree of scalability, regularity and symmetry. In this paper, using the construction method, we show that the OTIS-Network is Hamiltonian if the basic graph used for constructing the OTIS-Network is also Hamiltonian. Hamiltonicity is of great importance in the implementation of a verity of parallel algorithms such as those used for solving algebraic and graph problems, e.g. the interpolation Lagrange algorithm. Our results can also be applied to the Swapped Interconnection networks, a generalization of OTIS-Networks.

Important Links:

Go Back