Personne :
Bédard, Catherine

En cours de chargement...
Photo de profil
Adresse électronique
Date de naissance
Projets de recherche
Structures organisationnelles
Fonction
Nom de famille
Bédard
Prénom
Catherine
Affiliation
Université Laval. Département d'informatique et de génie logiciel
ISNI
ORCID
Identifiant Canadiana
ncf13720520
person.page.name

Résultats de recherche

Voici les éléments 1 - 1 sur 1
  • Publication
    Accès libre
    Problèmes d'homomorphisme à largeur de chemin bornée
    (2014) Bédard, Catherine; Tesson, Pascal
    Un homomorphisme est une fonction entre deux structures, par exemple des graphes, qui respecte certaines contraintes. Dans ce mémoire, on étudie la complexité des problèmes d'homomorphisme, c'est-à-dire des problèmes où l'on doit décider s'il existe une telle fonction entre deux structures. On présentera des propriétés sur ces structures qui permettent de déterminer cette complexité. On s'intéressera particulièrement aux problèmes d'homomorphisme qui appartiennent à la classe de complexité NL, une classe contenant des problèmes dont la résolution par un algorithme non déterministe nécéssite peu d'espace mémoire.