Skip to main content

Centre for Algorithms and Applications

Centre for Algorithms and Applications

The Centre is concerned with the study of various kinds of algorithms – parameterised, exact, randomised, heuristic and approximate – for problems arising in graph and hypergraph theory, constraint satisfaction, combinatorial optimisation, and their numerous applications.

Our current main focus is, from a theoretical perspective, in parameterised algorithms and computational complexity and, from the point of view of applications, in access control in information security.

Members

We have close collaborations with many researchers across the globe, including:

  • Paul Balister (University of Memphis, USA)
  • Joergen Bang-Jensen (Southern Denmark University)
  • Stephen A. Cook (University of Toronto, Canada)
  • Martin C. Cooper (University of Toulouse III, France)
  • Michael Forbes (University of Illinois at Urbana Champaign, USA)
  • Andrei Gagarin (Cardiff University, UK)
  • Peter G. Jeavons (Oxford University, UK)
  • Daniel Karapetyan (University of Essex, UK)
  • Stefan Kratsch (HU Berlin, Germany)
  • Tonnian Pitassi (University of Toronto, Canada)
  • M.S. Ramanujan (University of Warwick, UK)
  • Felix Reidl (Birkbeck University of London, UK)
  • Amir Shpilka (Tel Aviv University, Israel)
  • Angelika Steger (ETH Zurich, Switzerland)
  • Yuefang Sun (Shaoxing University, China)
  • Avi Wigderson (Institute of Advanced Studies, Princeton, USA)
  • Anders Yeo (Southern Denmark University)
  • Meirav Zehavi (Ben-Gurion University, Israel)
  • Xiaoyan Zhang (Nanjing Normal University, China)
  • Stanislav Zivny (Oxford University, UK)

Research strands

We are interested in various algorithms such as fixed-parameter, exact exponential, approximation and heuristic algorithms. We develop algorithms on graphs, digraphs and hypergraphs, for constraint satisfaction, combinatorial optimization and logic problems. In design and analysis of algorithms, we use graph-theoretical, combinatorial, algebraic, probabilistic and other methods.

For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.

algorithms 2

We are interested in classical and parameterized complexity, complexity of satisfiability, proof complexity, applications of logic in computer science, the interplay between algebra and computation, and the theory of SAT-solving. 

For our publications, see personal webpages of members of the centre, dblp, or Google Scholar. 

complexity 2

We are interested in directed, undirected, random, weighted, signed and other types of graphs as well as their generalizations such as hypergraphs, hypertournaments and directed hypergraphs. We study structural properties of graphs, algorithms on graphs and applications of graphs.

A recent book "Classes of Directed Graphs" edited by J. Bang-Jensen and G. Gutin (Springer, 2018, in print) consists of chapters devoted to various important classes of directed graphs and written by experts in these classes of digraphs.

For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.

graphs 2

We are interested in various access control problems. In particular, we have done significant research on the Workflow Satisfiability Problem (aka Constraint Satisfaction Problem in access control) designing efficient theoretical and practical algorithms to solve WSP and its generalization, the Bi-Objective WSP, which allows us to decide in cases when the WSP is unsatisfiable. We studied various constrains for WSP introducing a wide family of constraints, user-independent constraints, and resilience in WSP models. Our members received best papers awards at SACMAT 2015 and 2016 for WSP research.

For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.

security 2

Constraint satisfaction problems arise in many areas. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be formulated as CSPs. In any CSP there are variables which all have to be assigned values, subject to specified constraints. An equivalent way of defining CSPs is via homomorphisms between relational structures. We are interested understanding the computational complexity of constraint satisfaction problems, in particular, when CSPs and their generalizations (such as Valued CSPs) can be solved by efficient algorithms.

For our publications, see personal webpages of members of the centre, dblp, or Google Scholar.

csp 2

Grants

  • Gutin (PI), Cohen and Crampton (CoI's), Analyzing Security-aware Workflows, funded by the Leverhulme Trust, 2019 – 2021

    Network for Algorithms and Complexity in the UK (AlgoUK), funded by EPSRC, 2017 – 2020

  • Cohen (PI), Constraint Network Tractability: Beyond Structure and Language, funded by EPSRC, 2014 – 17

  • Gerke (PI), LMS conference grants, 2013 and 2016

  • Gutin (PI), Cohen and Crampton (CoI's), Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems, funded by EPSRC, 2013 – 2016

  • Tzameret (PI), New Approaches to the Limits of Efficient Propositional Reasoning: Foundations, Algorithms and Approximations, funded by The National Natural Science Foundation of China, 2014 – 2017

  • Wahlstrom (PI), Polytope methods in parameterized complexity, funded by EPSRC, 2017 – 18.

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

They say the two most important days of your life are the day you were born, and the day you find out why

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today