A Multipath Analysis of Biswapped Networks
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 >= 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 two 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 two 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.
biswapped networks interconnection networks connectivity cayley graphs otis networks hamiltonicity