Bounded Width Dichotomies in Constraint Satisfaction Problems

Simple item page
dc.contributor.advisorLaflamme, Claude
dc.contributor.advisorWoodrow, Robert E.
dc.contributor.authorLiprandi, Maximiliano
dc.contributor.committeememberCavers, Michael S.
dc.contributor.committeememberCockett, J. Robin B.
dc.contributor.committeememberBonato, Anthony
dc.date2018-11
dc.date.accessioned2018-06-11T19:44:28Z
dc.date.available2018-06-11T19:44:28Z
dc.date.issued2018-06-07
dc.description.abstractIn this thesis we examine the connection between structures with bounded width, polymorphisms and pebble games. There has been extensive work on trying to prove the dichotomy conjecture for finite structures, namely, the Constraint Satisfaction Problem (CSP) of a finite structure is either in P or NP-complete. We are interested in finding classes in which a stronger dichotomy exists; namely, where every structure has either bounded width or a hard CSP. We call this kind of dichotomy a bounded width dichotomy. We will investigate properties of polymorphisms of structures with bounded width, and use this to look at classes of directed graphs with a bounded width dichotomy.en_US
dc.identifier.citationLiprandi, M. (2018). Bounded Width Dichotomies in Constraint Satisfaction Problems (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/31986en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/31986
dc.identifier.urihttp://hdl.handle.net/1880/106758
dc.language.isoeng
dc.publisher.facultyGraduate Studies
dc.publisher.facultyScience
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subject.classificationEducation--Mathematicsen_US
dc.titleBounded Width Dichotomies in Constraint Satisfaction Problems
dc.typedoctoral thesis
thesis.degree.disciplineMathematics & Statistics
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameDoctor of Philosophy (PhD)
ucalgary.item.requestcopytrue
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2018_liprandi_maximiliano.pdf
Size:
777.7 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.74 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations