Using semidirect products of groups to build classes of interconnection networks (2020)
Journal Article
Stewart, I. (2020). Using semidirect products of groups to build classes of interconnection networks. Discrete Applied Mathematics, 283, 78-97. https://doi.org/10.1016/j.dam.2019.12.014

We build a framework within which we can define a wide range of Cayley graphs of semidirect products of abelian groups, suitable for use as interconnection networks and which we call toroidal semidirect product graphs. Our framework encompasses vario... Read More about Using semidirect products of groups to build classes of interconnection networks.

Variational networks of cube-connected cycles are recursive cubes of rings (2020)
Journal Article
Stewart, I. (2020). Variational networks of cube-connected cycles are recursive cubes of rings. Information Processing Letters, 157, Article 105925. https://doi.org/10.1016/j.ipl.2020.105925

In this short note we show that the interconnection networks known as variational networks of cube-connected cycles form a sub-class of the recursive cubes of rings.

Relating the bisection width of dual-port, server-centric datacenter networks and the solution of edge-isoperimetric problems in graphs (2019)
Journal Article
Erickson, A., Navaridas, J., & Stewart, I. (2020). Relating the bisection width of dual-port, server-centric datacenter networks and the solution of edge-isoperimetric problems in graphs. Journal of Computer and System Sciences, 108, 10-28. https://doi.org/10.1016/j.jcss.2019.08.005

Stellar datacenter networks are a recent generic construction designed to transform a base-graph into a dual-port, server-centric datacenter network. We prove that the S-bisection width of any stellar datacenter network can be obtained from the solut... Read More about Relating the bisection width of dual-port, server-centric datacenter networks and the solution of edge-isoperimetric problems in graphs.

INRFlow: An interconnection networks research flow-level simulation framework (2019)
Journal Article
Navaridas, J., Pascual, J. A., Erickson, A., Stewart, I. A., & Luján, M. (2019). INRFlow: An interconnection networks research flow-level simulation framework. Journal of Parallel and Distributed Computing, 130, 140-152. https://doi.org/10.1016/j.jpdc.2019.03.013

This paper presents INRFlow, a mature, frugal, flow-level simulation framework for modelling large-scale networks and computing systems. INRFlow is designed to carry out performance-related studies of interconnection networks for both high performanc... Read More about INRFlow: An interconnection networks research flow-level simulation framework.

The influence of datacenter usage on symmetry in datacenter network design (2017)
Journal Article
Stewart, I., & Erickson, A. (2018). The influence of datacenter usage on symmetry in datacenter network design. Journal of Supercomputing, 74(6), 2276-2313. https://doi.org/10.1007/s11227-017-2217-1

We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structur... Read More about The influence of datacenter usage on symmetry in datacenter network design.

On the combinatorial design of data centre network topologies (2017)
Journal Article
Stewart, I. (2017). On the combinatorial design of data centre network topologies. Journal of Computer and System Sciences, 89, 328-348. https://doi.org/10.1016/j.jcss.2017.05.015

The theory of combinatorial designs has recently been used in order to build switch-centric data centre networks incorporating a large number of servers, in comparison with the popular Fat-Tree data centre network. We clarify and extend these results... Read More about On the combinatorial design of data centre network topologies.

Improved routing algorithms in the dual-port datacenter networks HCN and BCN (2017)
Journal Article
Erickson, A., Stewart, I., Pascual, J., & Navaridas, J. (2017). Improved routing algorithms in the dual-port datacenter networks HCN and BCN. Future Generation Computer Systems, 75, 58-71. https://doi.org/10.1016/j.future.2017.05.004

We present significantly improved one-to-one routing algorithms in the datacenter networks HCN and View the MathML source in that our routing algorithms result in much shorter paths when compared with existing routing algorithms. We also present a mu... Read More about Improved routing algorithms in the dual-port datacenter networks HCN and BCN.

The stellar transformation: from interconnection networks to datacenter networks (2016)
Journal Article
Erickson, A., Stewart, I., Navaridas, J., & Kiasari, A. (2017). The stellar transformation: from interconnection networks to datacenter networks. Computer Networks, 113, 29-45. https://doi.org/10.1016/j.comnet.2016.12.001

The first dual-port server-centric datacenter network, FiConn, was introduced in 2009 and there are several others now in existence; however, the pool of topologies to choose from remains small. We propose a new generic construction, the stellar tran... Read More about The stellar transformation: from interconnection networks to datacenter networks.

Sufficient conditions for Hamiltonicity in multiswapped networks (2016)
Journal Article
Stewart, I. (2016). Sufficient conditions for Hamiltonicity in multiswapped networks. Journal of Parallel and Distributed Computing, 101, 17-26. https://doi.org/10.1016/j.jpdc.2016.10.015

OTIS networks are interconnection networks amenable to deployment as hybrid networks containing both electronic and optical links. Deficiencies as regards symmetry led to the subsequent formulation of biswapped networks which were later generalized t... Read More about Sufficient conditions for Hamiltonicity in multiswapped networks.

An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar (2016)
Journal Article
Erickson, A., Kiasari, A., Navaridas, J., & Stewart, I. (2016). An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar. IEEE Transactions on Parallel and Distributed Systems, 28(3), 689-703. https://doi.org/10.1109/tpds.2016.2591011

DPillar has recently been proposed as a server-centric datacenter network and is combinatorially related to (but distinct from) the well-known wrapped butterfly network. We explain the relationship between DPillar and the wrapped butterfly network be... Read More about An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar.

Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes (2016)
Journal Article
Kuo, C., & Stewart, I. (2016). Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes. Theoretical Computer Science, 627, 102-106. https://doi.org/10.1016/j.tcs.2016.02.029

Let F v and Fe be sets of faulty vertices and faulty edges, respectively, in the folded hypercube FQn so that |F v | + |Fe | ≤ n − 2, for n ≥ 2. Choose any fault-free edge e. If n ≥ 3 then there is a fault-free cycle of length l in FQn containing e,... Read More about Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes.

Graph editing to a fixed target (2014)
Journal Article
Golovach, P., Paulusma, D., & Stewart, I. (2017). Graph editing to a fixed target. Discrete Applied Mathematics, 216(Part 1), 181-190. https://doi.org/10.1016/j.dam.2014.07.008

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex di... Read More about Graph editing to a fixed target.

The expressibility of fragments of Hybrid Graph Logic on finite digraphs (2013)
Journal Article
Gate, J., & Stewart, I. (2013). The expressibility of fragments of Hybrid Graph Logic on finite digraphs. Journal of applied logic, 11(3), 272-288. https://doi.org/10.1016/j.jal.2013.05.002

Multiswapped networks and their topological and algorithmic properties (2013)
Journal Article
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

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 a... Read More about Multiswapped networks and their topological and algorithmic properties.

Interconnection networks of degree three obtained by pruning two-dimensional tori (2013)
Journal Article
Stewart, I. (2014). Interconnection networks of degree three obtained by pruning two-dimensional tori. IEEE Transactions on Computers, 63(10), 2473-9340. https://doi.org/10.1109/tc.2013.139

We study an interconnection network that we call 3Torus(m,n) obtained by pruning the 4m x 4n torus (of links) so that the resulting network is regular of degree 3. We show that 3Torus(m,n) retains many of the useful properties of tori (although, of c... Read More about Interconnection networks of degree three obtained by pruning two-dimensional tori.

A general technique to establish the asymptotic conditional diagnosability of interconnection networks (2012)
Journal Article
Stewart, I. (2012). A general technique to establish the asymptotic conditional diagnosability of interconnection networks. Theoretical Computer Science, 452, 132-147. https://doi.org/10.1016/j.tcs.2012.05.015

On the computational complexity of routing in faulty k-ary n-cubes and hypercubes. (2012)
Journal Article
Stewart, I. (2012). On the computational complexity of routing in faulty k-ary n-cubes and hypercubes. Parallel Processing Letters, 22(1), Article 1250003. https://doi.org/10.1142/s012962641250003x

We equate a routing algorithm in a (faulty) interconnection network whose underlying graph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixed source node to a fixed destination node, with the sub-digraph of (healthy) links... Read More about On the computational complexity of routing in faulty k-ary n-cubes and hypercubes..

Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption (2011)
Journal Article
Xiang, Y., & Stewart, I. (2011). Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption. IEEE Transactions on Parallel and Distributed Systems, 22(9), 1506-1513. https://doi.org/10.1109/tpds.2011.22

We prove that a k-ary 2-cube Q^k_2 with 3 faulty edges but where every vertex is incident with at least 2 healthy edges is bipancyclic, if k \geq 3, and k-pancyclic, if k \geq 5 is odd (these results are optimal). We go on to show that when k \geq 4... Read More about Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption.

A multipath analysis of biswapped networks (2011)
Journal Article
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

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 d... Read More about A multipath analysis of biswapped networks.

Augmented k-ary n-cubes (2011)
Journal Article
Xiang, Y., & Stewart, I. (2011). Augmented k-ary n-cubes. Information Sciences, 181(1), 239-256. https://doi.org/10.1016/j.ins.2010.09.005

We define an interconnection network AQn,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmen... Read More about Augmented k-ary n-cubes.