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, dominants-localisateurs et dominants-total-localisateurs ; Constant time generic algorithms for resolution of combinatorial optimization problems in the class of rotagraphs and fasciagraphs. Application to identifying codes, locating-dominating set and locating-total-dominating set
Titel:
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, dominants-localisateurs et dominants-total-localisateurs ; Constant time generic algorithms for resolution of combinatorial optimization problems in the class of rotagraphs and fasciagraphs. Application to identifying codes, locating-dominating set and locating-total-dominating set
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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. ; A fasciagraph of length n and of fiber F, is constituted of n consecutive copies of a graph F, each copy being linked to the next one according to a same scheme. Rotagraphs are defines similarily, but along a circular structure. In this thesis, we caracterize a set of combinatorial problems that can be efficiently solved when applied on the class of rotagraphs and fasciagraphs. In this context, we define closed and stable (d,q,w)-properties, and we present, for such ...