Sur des généralisations des graphes triangulés : application aux problèmes de satisfaction de contraintes / par Lamia Hadjadj Aoul ; sous la direction de Philippe Jégou

Auteur principal : Hadjadj Aoul, Lamia, 1970-, AuteurAuteur secondaire : Jégou, Philippe, Directeur de thèseAuteur secondaire collectivité : Université de Provence, Etablissement de soutenanceType de document : ThèseLangue : français.Pays: France.Éditeur : [S.l.] : [s.n.], 2003Description : 1 vol. (81 p.) : fig. ; 30 cmBibliographie : Bibliogr. p. 79-81.Sujet MSC : 05C85, Combinatorics - Graph theory, Graph algorithms
05C69, Combinatorics - Graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C90, Combinatorics - Graph theory, Applications of graph theory
68R10, Discrete mathematics in relation to computer science, Graph theory
97-02, Research exposition (monographs, survey articles) pertaining to mathematics education
Note de thèse: Thèse de doctorat, informatique et mathématiques, 2003, Aix-Marseille 1 Item type: Thèse
Tags from this library: No tags from this library for this title. Log in to add tags.
Holdings
Current library Call number Status Date due Barcode
CMI
Réserve
Thèses HAD (Browse shelf(Opens below)) Available 02468-01
CMI
Réserve
Thèses HAD (Browse shelf(Opens below)) Available 02468-02

Bibliogr. p. 79-81

Thèse de doctorat informatique et mathématiques 2003 Aix-Marseille 1

Le cadre de cette thèse est de caractériser certaines classes de graphes ayant de bonnes propriétés pour la résolution de systèmes de contraintes. En effet, nous étudions ici les propriétés et algorithmes de certaines classes de graphes qui se trouvent être des généralisations des graphes triangulés. En particulier, nous étudions dans le détail les graphes CSGk, qui définissent une hiérarchie de classes de graphes dont le second niveau, les graphes CSG1 sont exactement les graphes triangulés. Dans cette étude, nous essayons de voir si les résultats classiques des graphes triangulés peuvent ou non être généralisés, en particulier aux graphes CSG2. Nous étudierons notamment le théorème de Dirac ainsi que la définition par sous-graphes exclus. Dans la dernière partie, nous étudions les aspects algorithmiques relatifs aux graphes CSG2 pour trois questions. Tout d'abord leur reconnaissance, puis le calcul des cliques maximales, et enfin, l'opération qui consiste à ajouter des arêtes dans un graphe quelconque afin de construire un graphe CSG2 ; nous nommerons cette opération "2-triangulation". Il s'agit là d'outils algorithmiques qui trouvent leur justification notamment pour la généralisation de la méthode de décomposition de domaines par triangulation. La dernière contribution de cette thèse repose sur deux généralisations de classes polynomiales du problème de la clique : les graphes faiblement triangulés et les graphes de comparabilité. Ces généralisations sont construites sur le même principe que celui des graphes CSGk, à savoir une définition en termes de hiérarchie de classes de graphes. Aussi les différentes preuves s'appuient-elles sur le même type de schéma que pour les graphes CSG2, et les résultats que nous obtenons sont très similaires à ceux produits avec les graphes CSG2 en rapport principalement avec le problème de la clique

There are no comments on this title.

to post a comment.