Domain value mutation and other techniques for constraint satisfaction problems

Simple item page
dc.check.embargoformatNot applicableen
dc.check.infoNo embargo requireden
dc.check.opt-outNot applicableen
dc.check.reasonNo embargo requireden
dc.check.typeNo Embargo Required
dc.contributor.advisorBowen, Jamesen
dc.contributor.authorLikitvivatanavong, Chavalit
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderNational University of Singaporeen
dc.date.accessioned2017-05-11T09:09:13Z
dc.date.available2017-05-11T09:09:13Z
dc.date.issued2017
dc.date.submitted2017
dc.description.abstractThe 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.sponsorshipScience 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.description.statusNot peer revieweden
dc.description.versionAccepted Version
dc.format.mimetypeapplication/pdfen
dc.identifier.citationLikitvivatanavong, C. 2017. Domain value mutation and other techniques for constraint satisfaction problems. PhD Thesis, University College Cork.en
dc.identifier.endpage155en
dc.identifier.urihttps://hdl.handle.net/10468/3940
dc.language.isoenen
dc.publisherUniversity College Corken
dc.rights© 2017, Chavalit Likitvivatanavong.en
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/en
dc.subjectConstraint satisfaction problemsen
dc.subjectSearchen
dc.subjectGeneralized arc consistencyen
dc.subjectInterchangeabilityen
dc.thesis.opt-outfalse
dc.titleDomain value mutation and other techniques for constraint satisfaction problemsen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD (Science)en
ucc.workflow.supervisorj.bowen@cs.ucc.ie
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
LikitvivatanavongC_PhD2017_Abstract.pdf
Size:
21.7 KB
Format:
Adobe Portable Document Format
Description:
Abstract
Thumbnail Image
Name:
LikitvivatanavongC_PhD2017.pdf
Size:
1.39 MB
Format:
Adobe Portable Document Format
Description:
Full Text E-thesis
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
5.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Doctoral Theses
College of Science, Engineering and Food Science - Doctoral Theses
Computer Science - Doctoral Theses