Show item record

dc.contributor.advisorHahn, Gena
dc.contributor.advisorLarose, Benoît
dc.contributor.authorLemaître, Adrien
dc.date.accessioned2012-09-24T14:37:29Z
dc.date.availableNO_RESTRICTIONen
dc.date.available2012-09-24T14:37:29Z
dc.date.issued2012-09-04
dc.date.submitted2012-04
dc.identifier.urihttp://hdl.handle.net/1866/8585
dc.subjectcohérence d'arcen
dc.subjectdigraphesen
dc.subjecthomomorphisme avec listesen
dc.subjectpolymorphismeen
dc.subjectproblèmes de satisfaction de contraintesen
dc.subjectcomplexityen
dc.subjectdigraphen
dc.subjectlist-homomorphismen
dc.subjectpolymorphismen
dc.subjectconstraint satisfaction problemen
dc.subject.otherMathematics / Mathématiques (UMI : 0405)en
dc.titleComplexité des homomorphismes de graphes avec listesen
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiqueen
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelDoctorat / Doctoralen
etd.degree.namePh. D.en
dcterms.abstractLes problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2.en
dcterms.abstractConstraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.en
dcterms.languagefraen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record