Pour savoir comment effectuer et gérer un dépôt de document, consultez le « Guide abrégé – Dépôt de documents » sur le site Web de la Bibliothèque. Pour toute question, écrivez à corpus@ulaval.ca.
 

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
En cours de chargement...
Vignette d'image
PublicationAccè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.