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.
- 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.
- 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.
- Natasha Shakhlevich: Deterministic
scheduling theory, scheduling with controllable parameters, scheduling algorithms for distributed computing. Publications.
Kristina Vušković: Structural graph theory with algorithmic consequences.
There are many
opportunities for PhD research within the theme.