EPSRC logo

Details of Grant 

EPSRC Reference: EP/E048374/1
Title: Extending the Theory of Colour Graphs
Principal Investigator: Johnson, Dr M
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: Durham, University of
Scheme: First Grant Scheme
Starts: 12 November 2007 Ends: 11 May 2011 Value (£): 107,777
EPSRC Research Topic Classifications:
Fundamentals of Computing Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:  
Summary on Grant Application Form
Constrain Satisfaction Problems provide a framework for a wide variety of problems across a number of scientific disciplines. For example, the problems of scheduling use of shared experimental equipment such as space telescopes, of interpreting geometric information as required by modern drawing tools, and of designing the layout of silicon chips can all be seen as Constraint Satisfaction Problems.In general, it is difficult to solve such problem so researchers concentrate on expanding their knowledge of case that are tractable. Recently for a particular class of these problems progress has been made by considering a particular structure --- the solution graph --- that is associated with these problems. Our aim is to continue this progress by looking at solution graphs for a class of problems for which they have not previously been studied. It is hoped that this will lead to improved algorithms that will help us efficiently solve new problems.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: