Domain value mutation and other techniques for constraint satisfaction problems

Show simple item record

dc.contributor.advisor Bowen, James en Likitvivatanavong, Chavalit 2017-05-11T09:09:13Z 2017-05-11T09:09:13Z 2017 2017
dc.identifier.citation Likitvivatanavong, C. 2017. Domain value mutation and other techniques for constraint satisfaction problems. PhD Thesis, University College Cork. en
dc.identifier.endpage 155 en
dc.description.abstract The term Constraint Satisfaction Problem (CSP) refers to a class of NP-complete problems, a collection of difficult problems for which no fast solution is known. The standard definition of a CSP involves variables, values, and constraints: each variable must be assigned a value from a designated group of possible values (also known as the variable’s domain), while a constraint on a set of variables indicates permissible combinations of values for these variables. Given a CSP, an important objective is to query whether it has a solution — an assignment of each variable to a value such that all constraints are satisfied. Solving a CSP usually requires chronological backtracking search that interleaves variable assignments with various kinds of inferences in order to reduce the search space. This dissertation comprises two parts. The first part deals with a modification of the classical CSP model that allows a value to be broken up and multiple values to be combined. The second part deals with generalized arc consistency algorithms. Both parts share a common theme in that extensional constraints --‐ the most basic expression possible for constraints --- play the central role. Despite being an important class, extensional constraints have received much less attention recently as most efforts have been channelled toward identifying new types of specialized constraints and coming up with corresponding algorithms. Regardless, improvements to algorithms for extensional constraints are more fundamental. This dissertation will attempt to improve existing techniques and algorithms for extensional constraints by examining them critically from the bottom up and approaching them from a novel direction. en
dc.description.sponsorship Science Foundation Ireland (SFI Grant 00/PI.1/C075); National University of Singapore (Grant ARF 252-000-222-112 and MOE2012-T2-1-155) en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher University College Cork en
dc.rights © 2017, Chavalit Likitvivatanavong. en
dc.rights.uri en
dc.subject Constraint satisfaction problems en
dc.subject Search en
dc.subject Generalized arc consistency en
dc.subject Interchangeability en
dc.title Domain value mutation and other techniques for constraint satisfaction problems en
dc.type Doctoral thesis en
dc.type.qualificationlevel Doctoral en
dc.type.qualificationname PhD (Science) en
dc.internal.availability Full text available en No embargo required en
dc.description.version Accepted Version
dc.contributor.funder Science Foundation Ireland en
dc.contributor.funder National University of Singapore en
dc.description.status Not peer reviewed en Computer Science en
dc.check.type No Embargo Required
dc.check.reason No embargo required en
dc.check.opt-out Not applicable en
dc.thesis.opt-out false
dc.check.embargoformat Not applicable en
dc.internal.conferring Summer 2017 en

Files in this item

This item appears in the following Collection(s)

Show simple item record

© 2017, Chavalit Likitvivatanavong. Except where otherwise noted, this item's license is described as © 2017, Chavalit Likitvivatanavong.
This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement