Thesis icon

Thesis

Exploiting parallelism in decomposition methods for constraint satisfaction

Abstract:

Constraint Satisfaction Problems (CSPs) are NP-complete in general, however, there are many tractable subclasses that rely on the restriction of the structure of their underlying hypergraphs. It is a well-known fact, for instance, that CSPs whose underlying hypergraph is acyclic are tractable. Trying to define “nearly acyclic” hypergraphs led to the definition of various hypergraph decomposition methods. An important member in this class is the hypertree decomposition method, introduced by G...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Oxford college:
Merton College
Department:
Mathematical,Physical & Life Sciences Division - Computing Laboratory
Role:
Author

Contributors

Role:
Supervisor
Publication date:
2010
Type of award:
DPhil
Level of award:
Doctoral
URN:
uuid:30773f0c-9b53-4684-b1c4-2d20c2322edd
Local pid:
ora:6292

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP