Stewart, I.A. (2013) 'Multiswapped networks and their topological and algorithmic properties.', Journal of computer and system sciences., 79 (8). pp. 1269-1286.
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.
|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)
|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
|Look up in GoogleScholar|