Return to search

Tree-Representation of Set Families in Graph Decompositions and Efficient Algorithms

Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00340109
Date09 September 2008
CreatorsBui-Xuan, Binh-Minh
PublisherUniversité Montpellier II - Sciences et Techniques du Languedoc
Source SetsCCSD theses-EN-ligne, France
LanguageEnglish
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0017 seconds