Skip to main content

Research Repository

Advanced Search

Sufficient conditions for Hamiltonicity in multiswapped networks

Stewart, I.A.

Sufficient conditions for Hamiltonicity in multiswapped networks Thumbnail


Authors



Abstract

OTIS networks are interconnection networks amenable to deployment as hybrid networks containing both electronic and optical links. Deficiencies as regards symmetry led to the subsequent formulation of biswapped networks which were later generalized to multiswapped networks so as to still enable optoelectronic implementation (as it happens, multiswapped networks also generalize previously studied hierarchical crossed cubes). Multiswapped networks of the form Msw(H;G) are known to possess good (graph-theoretic) properties as regards their use as (optoelectronic) interconnection networks (in distributed-memory multiprocessors) and in relation to those of the component networks G and H. Combinatorially they provide a hierarchical mechanism to define new networks from existing networks (so that the properties of the new network can be controlled in terms of the constituent networks). In this paper we prove that if G and H are Hamiltonian networks then the multiswapped network Msw(H;G) is also Hamiltonian. At the core of our proof is finding specially designed Hamiltonian cycles in 2-dimensional and heavily pruned 3-dimensional tori, irrespective of the actual networks G and H we happen to be working with. This lends credence to the role of tori as fundamental networks within the study of interconnection networks.

Citation

Stewart, I. (2016). Sufficient conditions for Hamiltonicity in multiswapped networks. Journal of Parallel and Distributed Computing, 101, 17-26. https://doi.org/10.1016/j.jpdc.2016.10.015

Journal Article Type Article
Acceptance Date Oct 22, 2016
Online Publication Date Nov 9, 2016
Publication Date Nov 9, 2016
Deposit Date Oct 24, 2016
Publicly Available Date Nov 21, 2016
Journal Journal of Parallel and Distributed Computing
Print ISSN 0743-7315
Electronic ISSN 1096-0848
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 101
Pages 17-26
DOI https://doi.org/10.1016/j.jpdc.2016.10.015
Public URL https://durham-repository.worktribe.com/output/1372192
Related Public URLs http://community.dur.ac.uk/i.a.stewart/Papers/HamInMsns.pdf

Files







You might also like



Downloadable Citations