these

N d’ordre : 438N attribué par la bibliothèque : 07ENSL0438ÉCOLE NORMALE SUPÉRIEURE DE LYONLaboratoire de l’Informatique du ParallélismeTHÈSEprésentée et soutenue publiquement le 17 décembre 2007 parLaurent LYAUDETpour l’obtention du grade deDocteur de l’École Normale Supérieure de Lyonspécialité : Informatiqueau titre de l’École doctorale de mathématiques et d’informatique fondamentale de LyonGraphes et hypergraphes :complexités algorithmique et algébriqueDirecteurs de thèse : Jacques MAZOYERIoan TODINCAAprès avis de : Pierre FRAIGNIAUDStéphan THOMASSÉDevant la commission d’examen formée de :Alain BRETTO MembreArnaud DURANDePierre FRAIGNIAUD Membre/RapporteurJacques MAZOYEReStéphan THOMASSÉ MembrIoan TODINCA MembreÀ Arnaud et Vincent.RemerciementsJe tiens tout d’abord à remercier Vincent Bouchitté pour la qualité des en-seignements qu’il m’a donné en cryptologie et en théorie des graphes, pourm’avoir accepté comme stagiaire de DEA puis comme doctorant. Ce mémoireest dédié à la sienne ainsi qu’à celle de mon frère Arnaud.Je veux aussi remercier mes deux directeurs de thèse : Jacques Mazoyerpour m’avoir garanti dès le décés de Vincent que je pourrai finir ma thèseet Ioan Todinca pour avoir suivi de son mieux depuis Orléans mes avancéesscientifiques ainsi que pour ses relectures précises de mes articles et de ce ta-puscrit. Votre aide à tous deux m’a été précieuse.Je remercie Stéphan Thomassé et Pierre Fraigniaud d’avoir accepté ...