A multipath analysis of biswapped networks

Xiang, Y.; Stewart, I.A.

Abstract

Biswapped networks of the form $Bsw(G)$ have recently been proposed as interconnection networks to be implemented as optical transpose interconnection systems. We provide a systematic construction of $\kappa+1$ vertex-disjoint paths joining any two distinct vertices in $Bsw(G)$, where $\kappa\geq 1$ is the connectivity of $G$. In doing so, we obtain an upper bound of $\max\{2\Delta(G)+5,\Delta_\kappa(G)+\Delta(G)+2\}$ on the $(\kappa+1)$-diameter of $Bsw(G)$, where $\Delta(G)$ is the diameter of $G$ and $\Delta_\kappa(G)$ the $\kappa$-diameter. Suppose that we have a deterministic multipath source routing algorithm in an interconnection network $G$ that finds $\kappa$ mutually vertex-disjoint paths in $G$ joining any $2$ distinct vertices and does this in time polynomial in $\Delta_\kappa(G)$, $\Delta(G)$ and $\kappa$ (and independently of the number of vertices of $G$). Our constructions yield an analogous deterministic multipath source routing algorithm in the interconnection network $Bsw(G)$ that finds $\kappa+1$ mutually vertex-disjoint paths joining any $2$ distinct vertices in $Bsw(G)$ so that these paths all have length bounded as above. Moreover, our algorithm has time complexity polynomial in $\Delta_\kappa(G)$, $\Delta(G)$ and $\kappa$. We also show that if $G$ is Hamiltonian then $Bsw(G)$ is Hamiltonian, and that if $G$ is a Cayley graph then $Bsw(G)$ is a Cayley graph.

Citation

Xiang, Y., & Stewart, I. (2011). A multipath analysis of biswapped networks. The Computer Journal, 54(6), 920-930. https://doi.org/10.1093/comjnl/bxq083

• Journal Article Type: Article
• Publication Date: Jun 1, 2011
• Deposit Date: Oct 25, 2010
• Publicly Available Date: Oct 29, 2010
• Journal: The Computer Journal
• Print ISSN: 0010-4620
• Electronic ISSN: 1460-2067
• Publisher: BCS, The Chartered Institute for IT
• Peer Reviewed: Peer Reviewed
• Volume: 54
• Issue: 6
• Pages: 920-930
• DOI: https://doi.org/10.1093/comjnl/bxq083
• Keywords: Interconnection networks, OTIS networks, Biswapped networks, Connectivity, Hamiltonicity, Cayley graphs.
• Public URL: https://durham-repository.worktribe.com/output/1514766
• Publisher URL: http://www.dur.ac.uk/i.a.stewart/Papers/MultipathBiswappedNetworks.pdf