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: | PDF - Accepted Version (176Kb) |

Status: | Peer-reviewed |

Publisher Web site: | http://dx.doi.org/10.1093/comjnl/bxq083 |

Record Created: | 28 Oct 2010 12:50 |

Last Modified: | 18 Jan 2012 15:17 |

Social bookmarking: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |