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...
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Weitere Verfasser: | |
| Format: | Thèse et Mémoire papier |
| Sprache: | Français |
| Veröffentlicht: |
[S.l.] :
[s.n.]
2006.
|
| Schlagworte: | |
| Anmerkung: |
Publication autorisée par le jury |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Particular casses of graphs :, structural and algorithmic aspects |
| LEADER | 02792nam a22002777a 4500 | ||
|---|---|---|---|
| 001 | 239254 | ||
| 008 | 070420s2006 xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN114000425 | ||
| 041 | 0 | |a fre |b fre |b eng | |
| 084 | |a 004 | ||
| 100 | 1 | |a Ziti, Soumia, |d 1979- | |
| 240 | 1 | 0 | |a Particular casses of graphs : |b structural and algorithmic aspects |
| 245 | 1 | 0 | |a Classes particulières de graphes : |b aspects structurels et algorithmique |c par Soumia Ziti ; [sous la dir. de] M. Jean-Marie Vanherpe,... |
| 260 | |a [S.l.] : |b [s.n.], |c 2006. | ||
| 300 | |a 1 vol. (108 p.) : |b ill. ; |c 30 cm. | ||
| 500 | |a Publication autorisée par le jury | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2006 | ||
| 504 | |a Bibliogr. p. 99-105 | ||
| 520 | |a 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. | ||
| 650 | |a Algorithmes | ||
| 650 | |a Graphes, Théorie des | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Vanherpe, Jean-Marie. |4 ths | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 787 | 0 | 8 | |i Reproduced as: |0 246958464 |t Classes particulières de graphes |o aspects structurels et algorithmique |f par Soumia Ziti |c Lille |n Atelier national de reproduction des thèses |d 2006 |p Microfiches |s Lille-Thèses |
| 997 | |0 239254 |1 Thèse et Mémoire papier |a Ressource papier |c 0/Orléans/ |c 1/Orléans/BU Sciences, Technologies, STAPS/ |z Orléans, BU Sciences, Technologies, STAPS, TS 19-2006-37 |z Orléans, BU Sciences, Technologies, STAPS, TS 19-2006-37 b | ||