Algorithms and Complexity

The Algorithms and Complexity theme is led by Kristina Vušković. Research within the theme includes graph theory, algorithms on graphs and discrete structures, the computational complexity of problems on discrete structures, logic and proof complexity, deterministic scheduling theory and its applications, randomised algorithms, probabilistic analysis of algorithms, approximation algorithms and combinatorial optimisation.

The research interests of the individual members include:

  • Olaf Beyersdorff: Computational complexity, propositional proof complexity, satisfiability problems, bounded arithmetic, non-classical logics. Publications.
  • Martin Dyer: Sampling and counting, randomised algorithms, Markov chains, complexity theory, constraint satisfaction problems, random structures, probabilistic analysis, combinatorial optimisation. Publications.
  • Raymond Kwan: Public transport scheduling, integer linear programming, heuristics, meta-heuristics, hyper-heuristics. The research has led to Tracsis Plc, a Leeds University spin-out company. Publications.
  • Haiko Müller: Algorithms on graphs and partially ordered sets, fixed parameter algorithms, approximation algorithms, graph theory, special classes of graphs, width parameters of graphs. Publications.
  • Natasha Shakhlevich: Deterministic scheduling theory, scheduling with controllable parameters, scheduling algorithms for distributed computing. Publications.
  • Kristina Vušković: Structural graph theory with algorithmic consequences. Publications.

There are many opportunities for PhD research within the theme.