Liens externes
  • Répertoires
  • Facultés
  • Bibliothèques
  • Plan campus
  • Sites A-Z
  • Mon UdeM
    • Mon portail UdeM
    • Mon courriel
    • StudiUM
Dessin du pavillon Roger Gaudry/Sketch of Roger Gaudry Building
Site d'accueil de l'UniversitéSite d'accueil de l'UniversitéSite d'accueil de l'Université
Papyrus : Dépôt institutionnel
Papyrus
Dépôt institutionnel
Papyrus
    • français
    • English
  • français 
    • français
    • English
  • Ouvrir une session
  • français 
    • français
    • English
  • Ouvrir une session
Voir le document 
  •   Accueil
  • 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
  • Voir le document
  •   Accueil
  • 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
  • Voir le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Mon compte

Pour soumettre un document ou s'abonner à des alertes courriels
Ouvrir une session
Nouvel utilisateur?

Parcourir

Tout PapyrusCommunautés et CollectionsTitresDates de publicationAuteursDirecteurs de rechercheSujetsProgrammesAffiliationIndex des titresCette collectionTitresDates de publicationAuteursDirecteurs de rechercheSujetsProgrammesAffiliationIndex des titres

Statistiques

Données d'utilisation
Afficher les métadonnées
Permalien: http://hdl.handle.net/1866/8585

Complexité des homomorphismes de graphes avec listes

Thèse ou mémoire
Vignette
Lemaitre_Adrien_2012_these.pdf (780.6Ko)
2012-04 (octroi du grade: 2012-09-04)
Auteur(s)
Lemaître, Adrien
Directeur(s) de recherche
Hahn, Gena
Larose, Benoît
Cycle d'études
Doctorat
Programme
Informatique
Mots-clés
  • 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)
Résumé(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
Contactez-nous | Faire parvenir un commentaire
Certificat SSL / SSL Certificate
les bibliothéques/UdeM
  • Urgence
  • Vie privée
  • Offres d'emploi
  • Mon courriel
  • StudiUM
  • iTunes U
  • Nous écrire
  • Facebook
  • YouTube
  • Twitter
  • Fils des nouvelles UdeM
 

 


DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace
Contactez-nous | Faire parvenir un commentaire
Certificat SSL / SSL Certificate
les bibliothéques/UdeM
  • Urgence
  • Vie privée
  • Offres d'emploi
  • Mon courriel
  • StudiUM
  • iTunes U
  • Nous écrire
  • Facebook
  • YouTube
  • Twitter
  • Fils des nouvelles UdeM