# Staff Profile

## Professor Iain Stewart, MA PhD FBCS CITP

(email at i.a.stewart@durham.ac.uk)

### Biography

I am a Professor in the School of Engineering and Computing Sciences. 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.

I have a number of positions within the mathematics and computer science community which include the following: I am a member of the UK Computing Research Committee (UKCRC), having previously been on the Executive; I am a member of the Research Committee of the BCS Academy of Computing; I am a member of the EPSRC Computing College; I am an Editorial Advisor to the London Mathematical Society Journal of Computation and Mathematics; I am an Editor of the Journal of Discrete Algorithms; and I am an Associate Editor of The Computer Journal. In the past I have been: a Member of Council of the London Mathematical Society; Chair of the Computer Science Committee of the London Mathematical Society; Co-ordinator of the joint EPSRC and London Mathematical Society MathFIT (Mathematics for Information Technology) initiative; President of the British Colloquium for Theoretical Computer Science (BCTCS); and President of the European Association for Computer Science Logic (EACSL).

I have varied research interests including: computational complexity; finite model theory and descriptive complexity; graph theory and algorithms; interconnection networks for parallel and distributed computing; theoretical aspects of artificial intelligence; and group theory.

### Research Groups

#### Department of Computer Science

- Algorithms and Complexity

### Research Interests

- Computational complexity
- Finite model theory and descriptive complexity
- Graph theory and algorithms
- Group theory
- Interconnection networks for parallel and distributed computing
- Theoretical aspects of artificial intelligence

### Selected Publications

**1:**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.**2:**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.**3:****Stewart, I.A.**(1999). A perspective on Lindström quantifiers and oracles. In__Generalized Quantifiers and Computation: 9th European Summer School in Logic, Language, and Information ESSLLI’97Workshop Aix-en-Provence, France, August 11–22, 1997 Revised Lectures__. Väänänen, J. Berlin: Springer.**Lecture Notes in Computer Science Vol. 1754:**51-71.**4:**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.**5:**Puricella, A. &**Stewart, I.A.**(2001).__A generic greedy algorithm, partially-ordered graphs and NP-completeness__. 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'01, Rostock, Germany, Springer-Verlag.**6:****Stewart, I.A.**(2002). Program schemes, arrays, Lindstroem quantifiers and zero-one laws.*Theoretical Computer Science***275**(1-2): 283-310.**7:**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.**8:****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.**9:****Stewart, I.A.**(2003). The complexity of achievement and maintenance problems in agent-based systems.*Artificial Intelligence***146**(2): 175-191.**10:****Madelaine, F.R.**&**Stewart, I.A.**(2003). Some problems not definable using structure homomorphisms.*Ars Combinatoria***67**: 153-159.**11:**Puricella, A. &**Stewart, I.A.**(2003). Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.*Theoretical Computer Science***290**(3): 1897-1913.**12:**Arratia, A.A. &**Stewart, I.A.**(2003). A note on first-order projections and games.*Theoretical Computer Science***290**(3): 2085-2093.**13:**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.**14:****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.**15:**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.**16:****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.**17:****Madelaine, F.R.**&**Stewart, I.A.**(2007). Constraint satisfaction, logic and forbidden patterns.*SIAM Journal of Computing***37**(1): 132-163.**18:****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.**19:****Stewart, I.A.**(2008). On the fixed-parameter tractability of parameterized model-checking problems.*Information Processing Letters***106**(1): 33-36.**20:****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.**21:****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.**22:****Stewart, I.A.**(2009). Program schemes, queues, the recursive spectrum and zero-one laws.*Fundamenta Informaticae***91**(2): 411-435.**23:****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.**24:****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.**25:**Arratia-Quesada, A. &**Stewart, I.A.**(2009). On the power of deep pushdown stacks.*Acta Informatica***46**(7): 509-531.**26:****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.**27:****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.**28:****Stewart, I.A.**&**Xiang, Y.**(2010). One-to-many node-disjoint paths in (n,k)-star graphs.*Discrete Applied Mathematics***158**(1): 62-70.**29:****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.**30:****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.**31:**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.**32:****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.**33:**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.**34:****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.**35:****Xiang, Y.**&**Stewart, I.A.**(2011). Augmented k-ary n-cubes.*Information Sciences***181**(1): 239-256.**36:**Xiang, Y. &**Stewart, I.A.**(2011). A multipath analysis of biswapped networks.*The Computer Journal***54**(6): 920-930.**37:****Stewart, I.A.**(2012). On the computational complexity of routing in faulty k-ary n-cubes and hypercubes.*Parallel Processing Letters***22**(1): 1250003**38:****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.**39:**Stewart, I.A. (2012). A general technique to establish the asymptotic conditional diagnosability of interconnection networks.*Theoretical Computer Science***452**: 132-147.**40:****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.**41:****Stewart, I.A.**(2013). Multiswapped networks and their topological and algorithmic properties.*Journal of Computer and System Sciences***79**(8): 1269-1286.**42:****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**43:**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.**44:****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.**45:****Stewart, I.A.**(2014). Interconnection networks of degree three obtained by pruning two-dimensional tori.*IEEE Transactions on Computers***63**(10): 2473-2486.**46:****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.**47:****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.**48:**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.**49:****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.**50:****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.**51:****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.**52:**Kuo, C.-N. &**Stewart, I.A.**(2016). Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes.*Theoretical Computer Science***627**: 102-106.**53:****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.**54:****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.**55:****Stewart, I.A.**(2017). Sufficient conditions for Hamiltonicity in multiswapped networks.*Journal of Parallel and Distributed Computing***101**: 17-26.**56:****Stewart, I.A.**(2017). On the combinatorial design of data centre network topologies.*Journal of Computer and System Sciences***89**: 328-348.**57:****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.**58:**Golovach, P.A.,**Paulusma, D.**&**Stewart, I.A.**(2017). Graph editing to a fixed target.*Discrete Applied Mathematics***216**(Part 1): 181-190.**59:****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.**60:**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.**61:****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.**Stewart, I.A.**(2020). Using semidirect products of groups to build classes of interconnection networks.*Discrete Applied Mathematics***283**: 78-97.**Stewart, I.A.**(2020). Variational networks of cube-connected cycles are recursive cubes of rings.*Information Processing Letters***157**: 105925.

### Supervises

### Selected Grants

- 2009: EPSRC Grant "Quantified Constraints and Generalisations" £247,539
- 2009: EPSRC Grant "Tolerating faults in interconnection networks for parallel computing" £275,210
- 2006: EPSRC Grant "Finite and Algorithmic Model Theory", £19,000
- 2002: EPSRC Grant "The USe of Normal Forms For Solving Word Problems" £43,858
- 2001: EPSRC Grant "The Algebraic Structure of Complexity Classes" £43,619