Stewart, I.A. (2011) 'A multipath analysis of biswapped networks.', The computer journal., 54 (6). pp. 920-930.
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.
Item Type: | Article |
---|---|
Keywords: | Interconnection networks, OTIS networks, Biswapped networks, Connectivity, Hamiltonicity, Cayley graphs. |
Full text: | (AM) Accepted Manuscript Download PDF (176Kb) |
Status: | Peer-reviewed |
Publisher Web site: | http://dx.doi.org/10.1093/comjnl/bxq083 |
Date accepted: | No date available |
Date deposited: | 29 October 2010 |
Date of first online publication: | June 2011 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |