Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Multiswapped networks and their topological and algorithmic properties.

Stewart, I.A. (2013) 'Multiswapped networks and their topological and algorithmic properties.', Journal of computer and system sciences., 79 (8). pp. 1269-1286.

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.

Item Type:Article
Keywords:Interconnection networks, Hierarchical interconnection networks, OTIS networks, Biswapped networks, Multiswapped networks, Shortest paths, Connectivity, Cayley graphs
Full text:(AM) Accepted Manuscript
Download PDF
(285Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.jcss.2013.06.002
Publisher 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
Date accepted:No date available
Date deposited:28 June 2013
Date of first online publication:2013
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar