Classes particulières de graphes : aspects structurels et algorithmique
Dans cette thèse nous nous intéressons, d'abord, au principe de la décomposition des graphes qui permet de découper un graphe en sous graphes ayant des propriétés particulières et qui ont des liens spécifiés entre eux. Nous citons ainsi les méthodes de décompositions les plus importantes: décom...
Enregistré dans:
| Auteur principal: | |
|---|---|
| Autres auteurs: | |
| Format: | Thèse et Mémoire papier |
| Langue: | Français |
| Publié: |
[S.l.] :
[s.n.]
2006.
|
| Sujets: | |
| Note: |
Publication autorisée par le jury |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Particular casses of graphs :, structural and algorithmic aspects |
| Résumé: | Dans cette thèse nous nous intéressons, d'abord, au principe de la décomposition des graphes qui permet de découper un graphe en sous graphes ayant des propriétés particulières et qui ont des liens spécifiés entre eux. Nous citons ainsi les méthodes de décompositions les plus importantes: décomposition modulaire qui peut être appliquée à un graphe arbitraire, elle est un outil puissant pour résoudre plusieurs problèmes d'optimisation lorsqu on considère des classes particulières de graphes. Nous abordons aussi, des variantes de cette décomposition modulaire comme la décomposition en split et des classes particulières comme les cographes. Ensuite, la décomposition canonique qui est une adaptation de la décomposition modulaire au cas des graphes bipartis. Puis nous abordons le sujet des algorithmes dynamiques et leurs applications notamment à la classe des graphes bisplits étendus qui sont totalement décomposables par décomposition canonique. Finalement nous évoquons le sujet des graphes avec des configurations clairsemés en se basant sur la structure de P4 (chaîne de quatre sommets) et en étudiant la densité de présence de cette structure dans un graphe général comme les graphes P4-clairsemés ou (P4-clairsemés)-clairsemés, ou des situations analogues dans le cas des graphes bipartis comme le sont les graphes (P7, Star123)-clairsemés ou Star123-clairsemés. |
|---|---|
| Description: | Publication autorisée par le jury |
| Description matérielle: | 1 vol. (108 p.) : ill. ; 30 cm. |
| Bibliographie: | Bibliogr. p. 99-105 |