We use cookies on this site. By browsing our site you agree to our use of cookies. Close this message Find out more

Home > Computer Science home > News > New EPSRC Grant on Constraint Network Tractability
More in this section News articles

New EPSRC Grant on Constraint Network Tractability

Posted on 12/03/2014
Dave Cohen

Professor Dave Cohen

Professor Dave Cohen has been awarded an EPSRC Grant on "Constraint Network Tractability: Beyond Structure and Language".

Constraint Satisfaction is a very general way of specifying feasibility questions: Scheduling, Machine Vision, Timetabling, Machine Allocation, Delivery Routing  are all classic examples.

Such problems are computationally hard so a considerable effort has been invested into finding when particular classes may have practicable algorithms.  This work has been successful but has concentrated so far on restricting the structure or language allowed when specifying instances.

In this work Professor Cohen will be working with Professor Cooper from the University of Toulouse and Professor Jeavons and Dr Zivny from the University of Oxford to find a unifying theory for the known tractability results.  Their unique and ambitious contribution is to characterise tractable cases by forbidding small patterns which embody the reasons for hardness.  

The hope is that the list of such forbidden patterns is amenable to a unifying theory.  The team will be working on this research for three years.


Comment on this page

Did you find the information you were looking for? Is there a broken link or content that needs updating? Let us know so we can improve the page.

Note: If you need further information or have a question that cannot be satisfied by this page, please call our switchboard on +44 (0)1784 434455.

This window will close when you submit your comment.

Add Your Feedback