Skip to main content

Research Repository

Advanced Search

Multiswapped networks and their topological and algorithmic properties

Stewart, I.A.

Multiswapped networks and their topological and algorithmic properties Thumbnail


Authors



Abstract

We generalise the biswapped network Bsw(G)Bsw(G) to obtain a multiswapped network Msw(H;G)Msw(H;G), built around two graphs G and H. We show that the network Msw(H;G)Msw(H;G) lends itself to optoelectronic implementation and examine its topological and algorithmic. We derive the length of a shortest path joining any two vertices in Msw(H;G)Msw(H;G) and consequently a formula for the diameter. We show that if G has connectivity κ⩾1κ⩾1 and H has connectivity λ⩾1λ⩾1 where λ⩽κλ⩽κ then Msw(H;G)Msw(H;G) has connectivity at least κ+λκ+λ, and we derive upper bounds on the (κ+λ)(κ+λ)-diameter of Msw(H;G)Msw(H;G). Our analysis yields distributed routing algorithms for a distributed-memory multiprocessor whose underlying topology is Msw(H;G)Msw(H;G). We also prove that if G and H are Cayley graphs then Msw(H;G)Msw(H;G) need not be a Cayley graph, but when H is a bipartite Cayley graph then Msw(H;G)Msw(H;G) is necessarily a Cayley graph.

Citation

Stewart, I. (2013). Multiswapped networks and their topological and algorithmic properties. Journal of Computer and System Sciences, 79(8), 1269-1286. https://doi.org/10.1016/j.jcss.2013.06.002

Journal Article Type Article
Publication Date Dec 1, 2013
Deposit Date Jun 27, 2013
Publicly Available Date Mar 28, 2024
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 79
Issue 8
Pages 1269-1286
DOI https://doi.org/10.1016/j.jcss.2013.06.002
Keywords Interconnection networks, Hierarchical interconnection networks, OTIS networks, Biswapped networks, Multiswapped networks, Shortest paths, Connectivity, Cayley graphs

Files

Accepted Journal Article (291 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Journal of computer and system sciences. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Journal of computer and system sciences, 79 (8), 2013, 10.1016/j.jcss.2013.06.002





You might also like



Downloadable Citations