Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor
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.
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 |
Accepted Journal Article
(743 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© 2016 The Authors. Published by Elsevier Ltd. This is an open access article under the CC-BY license (http://creativecommons.org/licenses/by/4.0/).
Published Journal Article
(615 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Routing algorithms for recursively-defined data centre networks
(2015)
Presentation / Conference Contribution
Accelerating ant colony optimization-based edge detection on the GPU using CUDA
(2014)
Presentation / Conference Contribution
Improved routing in the data centre networks HCN and BCN
(2014)
Presentation / Conference Contribution
Improving Ant Colony Optimization performance on the GPU using CUDA.
(2013)
Presentation / Conference Contribution
Color image edge detection based on quantity of color information and implementation on the GPU.
(2011)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search