Feedback

Faculté des Sciences
Faculté des Sciences
MASTER THESIS
VIEW 121 | DOWNLOAD 353

Codes identifiants de graphes

Download
Vandermeer, Marion ULiège
Promotor(s) : Rigo, Michel ULiège
Date of defense : 27-Jun-2018 • Permalink : http://hdl.handle.net/2268.2/5008
Details
Title : Codes identifiants de graphes
Author : Vandermeer, Marion ULiège
Date of defense  : 27-Jun-2018
Advisor(s) : Rigo, Michel ULiège
Committee's member(s) : Charlier, Emilie ULiège
Mathonet, Pierre ULiège
Leroy, Julien ULiège
Language : French
Number of pages : 92
Keywords : [fr] Code identifiant
[fr] Théorie des graphes
[fr] Produit direct
[fr] Produit cartésien
[fr] Clique
[en] Identifying code
Discipline(s) : Physical, chemical, mathematical & earth Sciences > Mathematics
Target public : Researchers
Professionals of domain
Student
General public
Other
Institution(s) : Université de Liège, Liège, Belgique
Degree: Master en sciences mathématiques, à finalité spécialisée en statistique
Faculty: Master thesis of the Faculté des Sciences

Abstract

[fr] Les codes identifiants ont été introduits en 1998 par Karpovsky, Charkrabarty et Levitin dans le but de modéliser un problème d’identification de processeurs défectueux dans des réseaux multiprocesseurs.
Dans ce mémoire, nous nous intéressons au cardinal minimum que doit avoir un code identifiant d’un graphe. Cependant, ce problème est un problème difficile au niveau de la complexité : il n’est pas aisé de déterminer le cardinal minimum d’un code identifiant d’un graphe quelconque. Nous nous intéressons donc à des familles particulières de graphes pour lesquelles nous pouvons donner une valeur pour le cardinal minimum d’un code identifiant d’un graphe en fonction du nombre de sommets du graphe. Dans ce travail, nous avons donc choisi de travailler sur des graphes qui sont en réalité le produit de cliques : nous donnons une valeur, en fonction de la taille de ces cliques, pour le cardinal minimum d’un code identifiant du produit direct de deux cliques ainsi que pour le produit cartésien de cliques de même taille et de tailles différentes.
Enfin, nous concluons ce mémoire par un chapitre présentant les aspects plus généraux des codes identifiants : leurs applications, leur complexité, quelques variantes ainsi que des bornes pour le cardinal minimum d’un code identifiant d’un graphe quelconque.

[en] Identifying codes in graphs were introduced in 1998 by Karpovsky, Charkrabarty and Levitin in order to model fault-diagnosis in multiprocessor systems.
In this Master thesis, we are looking for the minimum cardinality of an identifying code of any graph. However, this issue is a difficult problem in terms of complexity: it is not straightforward to determine the minimum cardinality of an identifying code of any graph. We are therefore interested in particular families of graphs for which we can give a value for the minimum cardinality of an identifying code of a graph according to the number of vertices it contains. In the following, we decided to work on graphs that are actually the product of cliques: we give a value, according to the size of these cliques, for the minimum cardinality of an identifying code of the direct product of two cliques as well as for the Cartesian product of cliques of the same size and different sizes.

Finally, we conclude this Master thesis with a chapter presenting the more general aspects of identifying codes: their applications, their complexity, some variants as well as limits for the minimum cardinality of an identifying code of any graph.


File(s)

Document(s)

File
Access Memoire_MarionVandermeer_s122634.pdf
Description:
Size: 970.7 kB
Format: Adobe PDF

Author

  • Vandermeer, Marion ULiège Université de Liège > Master sc. math., à fin.

Promotor(s)

Committee's member(s)

  • Total number of views 121
  • Total number of downloads 353










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.