Liens externes
  • Directories
  • Faculties
  • Libraries
  • Campus maps
  • Sites A to Z
  • My UdeM
    • Mon portail UdeM
    • My email
    • StudiUM
Dessin du pavillon Roger Gaudry/Sketch of Roger Gaudry Building
University Home pageUniversity Home pageUniversity Home page
Papyrus : Institutional Repository
Papyrus
Institutional Repository
Papyrus
    • français
    • English
  • English 
    • français
    • English
  • Login
  • English 
    • français
    • English
  • Login
View Item 
  •   Home
  • Faculté des arts et des sciences
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires
  • View Item
  •   Home
  • Faculté des arts et des sciences
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

My Account

To submit an item or subscribe to email alerts.
Login
New user?

Browse

All of PapyrusCommunities and CollectionsTitlesIssue DatesAuthorsAdvisorsSubjectsDisciplinesAffiliationTitles indexThis CollectionTitlesIssue DatesAuthorsAdvisorsSubjectsDisciplinesAffiliationTitles index

Statistics

View Usage Statistics
Show metadata
Permalink: http://hdl.handle.net/1866/8585

Complexité des homomorphismes de graphes avec listes

Thesis or Dissertation
Thumbnail
Lemaitre_Adrien_2012_these.pdf (780.6Kb)
2012-04 (degree granted: 2012-09-04)
Author(s)
Lemaître, Adrien
Advisor(s)
Hahn, Gena
Larose, Benoît
Level
Doctoral
Discipline
Informatique
Keywords
  • cohérence d'arc
  • digraphes
  • homomorphisme avec listes
  • polymorphisme
  • problèmes de satisfaction de contraintes
  • complexity
  • digraph
  • list-homomorphism
  • polymorphism
  • constraint satisfaction problem
  • Mathematics / Mathématiques (UMI : 0405)
Abstract(s)
Les 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.
 
Constraint 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.
Collections
  • Thèses et mémoires électroniques de l’Université de Montréal [17173]
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires [732]

DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
Certificat SSL / SSL Certificate
les bibliothéques/UdeM
  • Emergency
  • Private life
  • Careers
  • My email
  • StudiUM
  • iTunes U
  • Contact us
  • Facebook
  • YouTube
  • Twitter
  • University RSS
 

 


DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
Certificat SSL / SSL Certificate
les bibliothéques/UdeM
  • Emergency
  • Private life
  • Careers
  • My email
  • StudiUM
  • iTunes U
  • Contact us
  • Facebook
  • YouTube
  • Twitter
  • University RSS