Algorithms and Complexity in Durham

Here you can find details of research projects for which we have obtained external funding. Click on a project title to find out more.

Network Alignment and Matching: Daniel Paulusma received in November 2023 a DSTL grant for a 3-month project with 4colors Ltd.
Promise Constraint Satisfaction Problem: Structure and Complexity: Andrei Krokhin received an EPSRC Fellowship for five years. This incorporates two postdoctoral positions in Durham. EPSRC Grant EP/X033201/1.
Algebraic Methods for Quantified Constraints: Barnaby Martin (PI), together with Catarina Carvalho (Herts, CI) and Hubie Chen (KCL, CI), received a grant to fund a postdoctoral researcher at Durham from January 2024 for three years. EPSRC Grant EP/X03190X/1.
KidneyAlgo: New Algorithms for UK and International Kidney Exchange. Daniel Paulusma was awarded a 2-year grant to run 2023 to 2025 to support a postdoctoral researcher. EPSRC EP/X01357X/, which is a Joint Project with David Manlove from the University of Glasgow (EP/X013618/1)
Balancing International Kidney Exchange. Daniel Paulusma was awarded a Leverhulme Trust Research Fellowship to run in 2023. RF-2022-607.
Graph Colouring: from Structure to Algorithms: Daniel Paulusma (PI) and Matthew Johnson (CI) were awarded an International Exchanges Grant to support work with Hans Bodlaender and others in the Algorithms and Complexity Group of Utrecht University from 15 September 2019 – 14 September 2021.

The Complexity of Promise Constraint Satisfaction: Andrei Krokhin (PI) and Daniel Paulusma (CI) received a grant to fund a postdoctoral researcher for three years. EPSRC Grant EP/R034516/1.

Cellular Automata and Boolean Networks: Max Gadouleau was awarded a grant to support work with Guillaume Theyssier from Aix-Marseille University for two years from February 2018. Royal Society-CNRS International Exchanges Scheme Cost Share Programme.

ALGOUK: Iain Stewart (PI) and Daniel Paulusma (CI) received support for three years from September 2017 to support a network that facilitates interactions within the UK’s research community and with researchers in industry or other academic disciplines. The network is hosted by research groups in Durham, King’s College London, Leicester, Liverpool, Royal Holloway and Warwick. EPSRC Grant EP/R005613/1.

Algorithmic Aspects of Temporal Graphs: George Mertzios received a grant to fund a postdoctoral researcher for three years. EPSRC Grant EP/P020372/1.

Efficient Graph Colouring Algorithms Via Input Restrictions: Daniel Paulusma (PI) and Matthew Johnson (CI) were awarded a grant to support a postdoctoral researcher for three years from September 2016. The Leverhulme Trust Research Project Grants.

Boolean Networks, Network Coding and Memoryless Computation: Max Gadouleau was awarded a grant to support work with Adrien Richard from Nice University for two years from January 2014. Royal Society International Exchanges Scheme Cost Share Programme.

Memoryless Computation and Network Coding: Max Gadouleau received a grant to fund a postdoctoral researcher (Alonso Castillo-Ramirez). EPSRC Grant EP/K033956/1.

Topology, Geometry and Laplacians of Simplicial Complexes: Stefan Dantchev, Ioannis Ivrissimtzis and Norbert Peyerimhoff (with Alina Vdovina (University of Newcastle)) received a grant to run for three years from June 2013 to fund a postdoctoral researcher. EPSRC Grant EP/K016687/1.

Detecting Induced Graph Patterns: Daniel Paulusma and Iain Stewart received a grant to run for three years from April 2013 to fund a postdoctoral researcher (Konrad Dąbrowski). EPSRC Grant EP/K025090/1.

Algorithmic Aspects of Intersection Graph Models: George Mertzios received a grant to run for two years from May 2013 to fund a postdoctoral researcher (Archontia Giannopoulou). EPSRC Grant EP/K022660/1.

Interconnection Networks: Practice unites with Theory (INPUT): Iain Stewart received funding to support a postdoctoral researcher (Alejandro Erickson) for three years from April 2013. EPSRC Grant EP/K015680/1.

Robustly Tractable Constraint Satisfaction Problems: Andrei Krokhin received funding to support a number of collaborative visits between October 2011 and September 2014. EPSRC Grant EP/J000078/1.

Coping with NP-Hardness: Parameterized and Exact Algorithms: Daniel Paulusma was awarded a grant to support work with Fedor Fomin from the University of Bergen, Norway from March 2011 to March 2013. Royal Society Joint Project Grant JP100692.

Scaling by Means of Ubiquitous Storage (Scalus): as members of a consortium of 15 academic and industrial partners, Tom Friedetzky (PI) and Hajo Broersma (CI) (later replaced by Matthew Johnson) were awarded a grant under the EU’s Marie Curie Initial Training Network scheme to fund two postgraduate students (Sepehr Meshkinfamfard and Foad Lotfifar) for three years from November 2010.

Submodular optimization, lattice theory and maximum constraint satisfaction problems: Andrei Krokhin was awarded a grant to support a postdoctoral researcher (Anna Huber) from July 2010 to December 2013. EPSRC Grant EP/H000666/1.

Approximation and mixing times in the ferromagnetic Potts model: Magnus Bordewich received a grant to run for three years from January 2010 to support the appointment of a postdoctoral researcher (Ross Kang). EPSRC Grant EP/G066604/1.

- The Parameterized Complexity of Reasoning Problems: Stefan Szeider was awarded a prestigious ERC Starting Grant to run for four years from January 2010. (The grant moved with Stefan to Vienna University of Technology.)

- Algorithmic Aspects of Graph Coloring: Daniel Paulusma (PI) and Hajo Broersma (CI) were awarded a grant to run from October 2009 to March 2013 to support a postdoctoral researcher (Petr Golovach) and a PhD student (Jian Song). EPSRC Grant EP/G043434/1.

- Quantified Constraints and Generalisations: Iain Stewart received support for a postdoctoral researcher (Barnaby Martin) for three years from September 2009. EPSRC Grant EP/G020604/1.

- Finding Shortcuts for Hard Reasoning Problems: Stefan Szeider was awarded a Research Fellowship from the Leverhulme Trust in 2009.

- Algorithmic Aspects of On-Line Graph Coloring: Daniel Paulusma was awarded a grant to support work with Jiri Fiala from Charles University, Prague from July 2009 to July 2011. Royal Society Joint Project Grant JP090172.

- Structural Vulnerability Measures for Networks and Graphs: Hajo Broersma received a grant to run from April 2009 to September 2012 to fund two postdoctoral researchers (Viresh Patel and Artem Pyatkin). EPSRC Grant EP/F064551/1.

- Descriptive Complexity of Constraints: An Algebraic Approach: Andrei Krokhin was awarded a grant to support research visits between Durham, Barcelona and Montreal. EPSRC Grant EP/G011001/1.

- Tolerating faults in interconnection networks for parallel computing: Iain Stewart was awarded a grant to support a postdoctoral researcher (Yonghong Xiang) for three years from February 2009. EPSRC Grant EP/G010587/1.

- WG 2008: 34th International Workshop on Graph-Theoretic Concepts in Computer Science: Hajo Broersma received funding to support us in hosting an international conference. EPSRC Grant EP/G012261/1.

- Extending the Theory of Colour Graphs: Matthew Johnson received a grant to run from November 2007 to May 2011 to support a postgraduate student (Ioannis Lignos). EPSRC Grant EP/E048374/1.

- Property Testing: Tom Friedetzky received a grant for the period October 2007 to March 2011 to fund a postgraduate student (Lars Nagel). EPSRC Grant EP/E029124/1.

- Fixed-parameter algorithms and satisfiability: Stefan Szeider’s grant funded a postgraduate student (Luke Mathieson) for three and a half years from October 2006. EPSRC Grant EP/E001394/1.

- Randomised algorithms and approximation in phylogenetics: Magnus Bordewich held a Postdoctoral Research Fellowship for three years from October 2006. EPSRC Grant EP/D063574/1.

- Exact algorithms for NP-hard problems: Daniel Paulusma was awarded a grant to run from September 2006 to March 2010 to fund a PhD student (Pim van ‘t Hof). EPSRC Grant EP/D053633/1.

- Theory of Generalised Nets: Stefan Dantchev was awarded a Royal Society Joint Project Grant to support a collaboration with Krassimir Atanassov from Bulgarian Academy of Sciences, Sofia from 2007 to 2009.

- A general theory of colour graphs: Matthew Johnson received an award from the Nuffield Foundation’s Newly Appointed Science Lecturers scheme to support his work in 2006. Nuffield Grant NAL/32772.

- Complexity Gaps in Propositional Proof Complexity: Stefan Dantchev was awarded a grant to support a postdoctoral researcher (Barnaby Martin) from September 2005 to February 2008. EPSRC Grant EP/C526120/1.

- Constraint Satisfaction Problems: Complexity and Approximability: Andrei Krokhin was an EPSRC Advanced Fellow between 2005 and 2010. EPSRC Grant EP/C543831/1.

- Parameterized algorithms for automated reasoning, constraint satisfaction and related areas: Stefan Szeider received an award from the Nuffield Foundation’s Newly Appointed Science Lecturers scheme to support his work in 2005. Nuffield Grant NAL/01012/G.