Abstract FR:

Cette these est une contribution a la resolution de quelques problemes de couplage dans les graphes par des algorithmes paralleles efficaces. L'importance de ces problemes est double : theorique (le couplage peut etre utilise comme routine pour la resolution d'autres problemes de graphes comme la recherche en profondeur) et pratique (utilises pour modeliser des problemes de reconnaissance de formes, d'affectation). D'un point de vue algorithmique sequentiel, les problemes de couplage sont efficacement resolus. Par contre, d'un point de vue traitement parallele, la plupart d'entre eux restent mal resolus. Nous donnons dans cette these un certain nombre de resultats montrant que pour certaines familles de graphes bien particulieres, il est possible de resoudre efficacement ces problemes. Nous donnons aussi les algorithmes paralleles correspondants. Ces familles de graphes n'admettaient aucune solution auparavant. Nous avons aussi etudie deux problemes connexes a ceux des couplages dans les graphes qui sont la persistance et l'extensibilite. Pour l'extensibilite, nous proposons le premier algorithme sequentiel polynomial quand les graphes consideres sont bipartis. D'autre part, nous proposons des algorithmes paralleles efficaces pour la resolution de ces deux problemes.