# Staff profile

## Professor Iain Stewart

Professor

MA PhD FBCS CITP

Affiliation | Room number | Telephone |
---|---|---|

Professor in the Department of Computer Science | MCS 2005 | +44 (0) 191 33 41720 |

### Biography

I am a * Professor* in the

**. I read mathematics at Christ Church, Oxford (1980-83) before completing my PhD in mathematics at Queen Mary College, University of London (1983-86). I was then appointed to a Lecturership in the Computing Laboratory, University of Newcastle upon Tyne in 1986 before moving to a Lecturership in the Department of Computer Science, University of Wales Swansea in 1992. I was later appointed Senior Lecturer (1994) and then Reader (1995) before becoming Professor of Computer Science at Leicester in 1996. I moved to the Department of Computer Science at Durham as Professor in 2002.**

*Department of Computer Science*Whilst at Leicester, I was * Head of the School of Mathematics and Computer Science* from 1999-2002 and at Durham I have twice been

*: from 2003-2006 and for 6 months in 2008. I was*

**Head of Computer Science***for the School of Engineering and Computing Sciences from 2011-2014 (there was a joint school 2009-2017) but as of 2017 the School of Engineering and Computing Sciences is no more with the Department of Computer Science reconstituted. I was*

**Director of Research***for the new department from 2019-2021.*

**Director of Research**I was a **Computer Science and Informatics Panel**** Member** of HEFCE’s

**(**

*Research Excellence Framework**) in*

**REF****and again in**

*REF 2014***. REF is the system for assessing the quality of research in UK higher education institutions and replaced the Research Assessment Exercise (RAE).**

*REF 2021*I have been a Member of * UK Computing Science Research Committee* (

*) since 2002 and was a Member of the*

**UKCRC***2004-2007. As of October 2013, I rejoined the*

**Executive Committee****before standing down at the end of my term in 2016. UKCRC is an expert panel of the Institution of Engineering and Technology (IET) and the British Computing Society (BCS), and aims to promote the vitality, quality and impact of Computing Research in the UK.**

*Executive Committee*I have served the * London Mathematical Society* (

*) for some years having been: a*

**LMS***1996-99 and*

**Member of LMS Computer Science Committee***1999-2002; a*

**Chair***1997-99; and a*

**Member of LMS Publications Committee***1997-1999. I was also*

**Member of LMS Council***of the joint*

**Coordinator***(*

**LMS/EPSRC Mathematics for IT***) initiative 2000-2002. As of November 2013, I resumed LMS service and was elected to*

**MathFIT***. I also joined the*

**LMS Council***in February 2014. In January 2015 I became*

**Computer Science Committee***, chairing (the now defunct)*

**Programme Secretary***. I stepped down from Council and from being Programme Secretary in November 2018 and from chairing the*

**Programme Committee***in November 2019. The LMS was founded in 1865 and is the major UK learned society for Mathematics.*

**Society Lectures and Meetings Committee**(**SLAM**)The * BCS Academy of Computing* is a learned society dedicated to advancing computing as an academic discipline. The Academy mission is to advance the creation, study and application of knowledge in computing for the benefit of society. I was a

*, which is the most senior committee within the Academy, before resigning in 2016. I am also a*

**Member of BCS Academy Board***.*

**Fellow of the BCS**In deciding how best to meet the needs of peer review of research proposals, the * EPSRC* established a college of experts, nominated by those active in the research field concerned, to provide a broadly based community from which to obtain peer review advice. I am a member of the

*and have been since its inauguration.*

**EPRSC Peer Review College**The * Computer Journal* was established in 1958 and is published by Oxford University Press on behalf of the BCS. It is split into four sections and publishes research papers in a full range of subject areas, as well as regular feature articles and occasional themed issues. The journal provides a complete overview of developments in the field of Computer Science. I have been an Associate Editor for some years but in January 2014 I became

*of*

**Section Editor***. I stood down*

**Section A: Computer Science Theory, Methods and Tools****at the end of 2021.**

The * Philosophical Transactions of the Royal Society A* was founded in 1660 and is the world’s first scientific journal. It publishes high quality theme issues on topics of current importance and general interest within the physical, mathematical, and engineering sciences. As of January 2017, I joined its

*.*

**Editorial Board**I was a member of the * Advisory Board* of the Springer book series

**(**

*Undergraduate Topics in Computer Science**) for many years before standing down at the end of 2021.*

**UTICS**I have previously been: ** President** of the

*(*

**British Colloquium for Theoretical Computer Science***);*

**BCTCS****of the**

*President**(*

**European Association for Computer Science Logic***); an editorial board member of the (now defunct)*

**EACSL***(as published by Elsevier); and an editor of the (now defunct)*

**Journal of Discrete Algorithms****(as published by CUP).**

*LMS Journal of Computation and Mathematics*### Research interests

- graph theory and algorithms
- interconnection networks for parallel and distributed computing
- theoretical aspects of artificial intelligence
- group theory
- computational complexity
- finite model theory and descriptive complexity

### Research groups

- ACiD: Algorithms and Complexity

### Publications

Chapter in book

Conference Paper

- Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I.A. & Trehan, A. (2023), Payment scheduling in the interval debt model,
__48th Int. Conf. on Current Trends in Theory and Practice of Computer Science__. Novy Smokovec, Slovakia, Springer. - Stewart, I.A. (2015), On the mathematics of data centre network topologies, in Kosowski, A. & Walukiewicz, I. eds, Lecture Notes in Computer Science
**9210**:__20th International Symposium on Fundamentals of Computation Theory__. Gdańsk, Poland, Springer, Cham, 283-295. - Kiasari, A.E., Navaridas, J. & Stewart, I.A. (2015), Routing packets on DPillar data centre networks, in Wang, G., Zomaya, A., Perez, G.M. & Li, K. eds, Lecture Notes in Computer Science
**9531**:__15th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP__. Zhangjiajie, China, Springer, 329-343. - Erickson, A., Kiasari, A.E., Navaridas, J. & Stewart, I.A. (2015), An efficient shortest path routing algorithm in the data centre network DPillar, in Lu, Z., Kim, D., Wu, W., Li, W. & Du, D.-Z. eds, Lecture Notes in Computer Science
**9486**:__9th Annual International Conference on Combinatorial Optimization and Applications, COCOA__. Houston, USA, Springer, 209-220. - Erickson, A., Kiasari, A., Navaridas, J. & Stewart, I.A. (2015), Routing algorithms for recursively-defined data centre networks,
**3**:__13th IEEE International Symposium on Parallel and Distributed Processing with Applications__. Helsinki, IEEE Computer Society Press, Piscataway, NJ, 84-91. - Stewart, I.A. (2014), Improved routing in the data centre networks HCN and BCN,
__2nd International Symposium on Computing and Networking - Across Practical Development and Theoretical Research__. Shizuoka, Japan, IEEE Computer Society Press, Shizuoka, 212-218. - Dawson, L. & Stewart, I.A. (2014), Accelerating ant colony optimization-based edge detection on the GPU using CUDA,
__2014 IEEE Congress on Evolutionary Computation (CEC)__. Beijing, China, IEEE, Piscataway, NJ, 1736-1743. - Dawson, L. & Stewart, I.A. (2013), Improving Ant Colony Optimization performance on the GPU using CUDA,
__2013 IEEE Congress on Evolutionary Computation__. Cancun, Mexico, IEEE, 1901-1908 - Dawson, L. & Stewart, I.A. (2013), Candidate set parallelization strategies for Ant Colony Optimization on the GPU, in Kołodziej, J., Di Martino, B., Talia,D. & Xiong, K. eds, Lecture Notes in Computer Science
**8285**:__13th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP'13__. Vietri sul Mare, Springer, Cham, 216-225. - Golovach, P., Paulusma, D. & Stewart, I.A. (2013), Graph editing to a fixed target, in Lecroq, T. & Mouchard, L. eds, Lecture Notes in Computer Science
**8288**:__International Workshop on Combinatorial Algorithms__. Rouen, France, Springer, Rouen, 192-205. - Xiang, Y., Stewart, I.A. & Madelaine, F.R. (2012), Node-to-node disjoint paths in k-ary n-cubes with faulty edges,
__17th International Conference on Parallel and Distributed Systems, ICPADS'11__. Tainan, Taiwan, IEEE Computer Society, Piscataway, 181-187. - Stewart, I.A. (2011), Hamiltonian cycles through prescribed edges in k-ary n-cubes, in Wang, W., Zhu, X. & Du, D.-Z. eds, Lecture Notes in Computer Science Vol. 6831
**6831**:__5th Annual International Conference on Combinatorial Optimization and Applications, COCOA'11__. Zhangjiajie, China, Springer, Berlin, 82-97. - Zhao, J., Xiang, Y., Dawson, L. & Stewart, I.A. (2011), Color image edge detection based on quantity of color information and implementation on the GPU, in Gonzalez, T. eds,
__23rd IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS'11__. Dallas, USA, Acta Press, 116-123. - Stewart, I.A. (2010), A general algorithm for detecting faults under the comparison diagnosis model,
__24th IEEE International Parallel and Distributed Processing Symposium, IPDPS'10,__. Atlanta, Georgia, U.S.A., IEEE Computer Society Press, Piscataway, 1-9. - Gate, J. & Stewart. I.A. (2010), Frameworks for logically classifying polynomial-time optimisation problems, in Ablayev F. & Mayr E.F. eds, Lecture Notes in Computer Science
**6072**:__Proceedings of 5th International Computer Science Symposium in Russia__. Kazan, Russia, Springer-Verlag, Berlin, 120-131. - Xiang, Y. & Stewart, I.A. (2009), Pancyclicity in faulty k-ary 2-cubes,
__21st International Conference on Parallel and Distributed Computing and Systems, PDCS'09__. Cambridge, Massachusetts, USA, Acta Press, Cambridge MA 77-84. - Xiang, Y. & Stewart, I.A. (2009), Pancyclicity and panconnectivity in augmented k-ary n-cubes,
__The Fifteenth International Conference on Parallel and Distributed Systems (ICPADS'09)__. Shenzhen, China, IEEE Computer Society, Los Alamitos, 308-315. - Broersma, H., Johnson, M., Paulusma, D. & Stewart, I.A. (2006), The computational complexity of the parallel knock-out problem, Lecture Notes in Computer Science
**3887**:__7th Latin American Theoretical Informatics Symposium (LATIN 2006)__. Valdivia, Chile., Springer, Berlin, 250-261.

Conference Proceeding

Journal Article

- Stewart, I.A. (2020). Variational networks of cube-connected cycles are recursive cubes of rings.
*Information Processing Letters***157**: 105925. - Stewart, I.A. (2020). Using semidirect products of groups to build classes of interconnection networks.
*Discrete Applied Mathematics***283**: 78-97. - Erickson, A., Navaridas, J. & Stewart, I.A. (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. - Navaridas, Javier, Pascual, Jose A., Erickson, Alejandro, Stewart, Iain A. & Luján, Mikel (2019). INRFlow: An interconnection networks research flow-level simulation framework.
*Journal of Parallel and Distributed Computing***130**: 140-152. - Stewart, I.A. & Erickson, A. (2018). The influence of datacenter usage on symmetry in datacenter network design.
*The Journal of Supercomputing***74**(6): 2276-2313. - Stewart, I.A. (2017). On the combinatorial design of data centre network topologies.
*Journal of Computer and System Sciences***89**: 328-348. - Erickson, A., Stewart, I.A., Pascual, J.A. & Navaridas, J. (2017). Improved routing algorithms in the dual-port datacenter networks HCN and BCN.
*Future Generation Computer Systems***75**: 58-71. - Erickson, A., Stewart, I.A., Navaridas, J. & Kiasari, A.E. (2017). The stellar transformation: from interconnection networks to datacenter networks.
*Computer Networks***113**: 29-45. - Golovach, P.A., Paulusma, D. & Stewart, I.A. (2017). Graph editing to a fixed target.
*Discrete Applied Mathematics***216**(Part 1): 181-190. - Stewart, I.A. (2017). Sufficient conditions for Hamiltonicity in multiswapped networks.
*Journal of Parallel and Distributed Computing***101**: 17-26. - Erickson, A., Kiasari, A.E., Navaridas, J. & Stewart, I.A. (2016). An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar.
*IEEE Transactions on Parallel and Distributed Systems***28**(3): 689-703. - Kuo, C.-N. & Stewart, I.A. (2016). Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes.
*Theoretical Computer Science***627**: 102-106. - Stewart, I.A. (2014). Interconnection networks of degree three obtained by pruning two-dimensional tori.
*IEEE Transactions on Computers***63**(10): 2473-2486. - Gate, J. & Stewart, I.A. (2013). The expressibility of fragments of Hybrid Graph Logic on finite digraphs.
*Journal of Applied Logic***11**(3): 272-288. - Stewart, I.A. (2013). Multiswapped networks and their topological and algorithmic properties.
*Journal of Computer and System Sciences***79**(8): 1269-1286. - Stewart, I.A. (2012). A general technique to establish the asymptotic conditional diagnosability of interconnection networks.
*Theoretical Computer Science***452**: 132-147. - Stewart, I.A. (2012). On the computational complexity of routing in faulty k-ary n-cubes and hypercubes.
*Parallel Processing Letters***22**(1): 1250003 - Xiang, Y. & Stewart, I.A. (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. - Xiang, Y. & Stewart, I.A. (2011). Augmented k-ary n-cubes.
*Information Sciences***181**(1): 239-256. - Xiang, Y. & Stewart, I.A. (2011). A multipath analysis of biswapped networks.
*The Computer Journal***54**(6): 920-930. - Stewart, I.A. & Xiang, Y. (2010). One-to-many node-disjoint paths in (n,k)-star graphs.
*Discrete Applied Mathematics***158**(1): 62-70. - Lai, P.-L., Hsu, H.-C., Tsai, C.-H. & Stewart, I.A. (2010). A class of hierarchical graphs as topologies for interconnection networks.
*Theoretical Computer Science***411**(31-33): 2912-2924. - Stewart, I.A. & Xiang, Y. (2009). Bipanconnectivity and bipancyclicity in k-ary n-cubes.
*IEEE Transactions on Parallel and Distributed Systems***20**(1): 25-33. - Stewart, I.A. (2009). Logical and complexity-theoretic aspects of models of computation with restricted access to arrays.
*Journal of Logic and Computation***19**(1): 217-242. - Arratia-Quesada, A. & Stewart, I.A. (2009). On the power of deep pushdown stacks.
*Acta Informatica***46**(7): 509-531. - Stewart, I.A. (2009). Program schemes, queues, the recursive spectrum and zero-one laws.
*Fundamenta Informaticae***91**(2): 411-435. - Madelaine, F.R. & Stewart, I.A. (2008). Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies.
*Discrete Mathematics***308**(18): 4144-4164. - Stewart, I.A. & Xiang, Y. (2008). Embedding long paths in k-ary n-cubes with faulty nodes and links.
*IEEE Transactions on Parallel and Distributed Systems***19**(8): 1071-1085. - Broersma, H., Johnson, M., Paulusma, D. & Stewart, I.A. (2008). The computational complexity of the parallel knock-out problem.
*Theoretical Computer Science***393**(1-3): 182-195. - Stewart, I.A. (2008). On the fixed-parameter tractability of parameterized model-checking problems.
*Information Processing Letters***106**(1): 33-36. - Madelaine, F.R. & Stewart, I.A. (2007). Constraint satisfaction, logic and forbidden patterns.
*SIAM Journal of Computing***37**(1): 132-163. - Stewart, I.A. (2007). Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links.
*Journal of Interconnection Networks***8**(3): 253-284. - Gault, R.L. & Stewart, I.A. (2006). An infinite hierarchy in a class of polynomial-time program schemes.
*Theory of Computing Systems***39**(5): 753-783. - Feder, T., Madelaine, F.R. & Stewart, I.A. (2004). Dichotomies for classes of homomorphism problems involving unary functions.
*Theoretical Computer Science***314**(1-2): 1-43. - Puricella, A. & Stewart, I.A. (2003). Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.
*Theoretical Computer Science***290**(3): 1897-1913. - Stewart, I.A. (2003). The complexity of achievement and maintenance problems in agent-based systems.
*Artificial Intelligence***146**(2): 175-191. - Stewart, I.A. (2003). Using program schemes to capture polynomial-time logically on certain classes of structures.
*London Mathematical Society Journal of Computation and Mathematics***6**: 40-67. - Arratia, A.A. & Stewart, I.A. (2003). A note on first-order projections and games.
*Theoretical Computer Science***290**(3): 2085-2093. - Madelaine, F.R. & Stewart, I.A. (2003). Some problems not definable using structure homomorphisms.
*Ars Combinatoria***67**: 153-159. - Stewart, I.A. (2002). Program schemes, arrays, Lindstroem quantifiers and zero-one laws.
*Theoretical Computer Science***275**(1-2): 283-310. - Ashir, Y.A. & Stewart, I.A. (2002). Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes.
*SIAM Journal On Discrete Mathematics***15**(3): 317-328. - Gault, R.L. & Stewart, I.A. (2001). On a hierarchy involving transitive closure logic and existential second-order quantification.
*Logic Journal of the IGPL***9**(6): 769-780. - Arratia-Quesada, A.A., Chauhan, S.R. & Stewart, I.A. (1999). Hierarchies in classes of program schemes.
*Journal of Logic and Computation***9**(6): 915-957. - Chauhan, S.R. & Stewart, I.A. (1999). On the power of built-in relations in certain classes of program schemes.
*Information Processing Letters***69**(2): 77-82.