Aller au menu Aller au contenu
Consultez les publications et les thèses
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Consultez les publications et les thèses
Consultez les publications et les thèses

> GSCOP_RESULTATS > GSCOP_ThèsesSoutenues

Thèse Marwane BOUZNIF

Auteur : Marwane BOUZNIF
Directeur de thèse : Myriam PREISMANN
Codirigée par Julien MONCEL
Date : 4 juillet 2012

Algorithmes génériques en temps constant pour la résolution de problèmes combinatoires dans la classe des rotagraphes et fasciagraphes. Application aux codes identifiants, dominant-localisateurs et dominant-total-localisateurs.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives
du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle.

Mots clés :  thèorie des graphes, optimisation combinatoire, grilles, fasciagraphes, rotagraphes, complexité algorithmique, NP-complétude, graphes fractals, codes identifiants, dominant-localisateur, dominant-total-localisateurs.

mise à jour le 13 novembre 2012

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Univ. Grenoble Alpes