Multiswapped networks and their topological and algorithmic properties

Stewart, I.A.

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: Jun 28, 2013
• 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