Algorithms and Complexity in Durham

ACiD

Algorithms and Complexity in Durham
A research group in the School of Engineering and Computing Sciences

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

Topology, Geometry and Laplacians of Simplicial Complexes: Norbert Peyerimhoff and Stefan Dantchev (with Ioannis Ivrissimtzis and Alina Vdovina) 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. 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. EPSRC Grant EP/K022660/1.

Interconnection Networks: Practice unites with Theory (INPUT): Iain Stewart received funding to support a postdoctoral research 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.

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.

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.

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.

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.