Bruce Reed

mathématicien et informaticien canadien

Bruce Alan Reed, né en 1962, est un mathématicien et informaticien canadien, titulaire de la Chaire de Recherche du Canada en théorie des graphes et professeur d'informatique à l'Université McGill[1].

Bruce Reed
Bruce Reed à l'Institut de Recherche de Bellairs en 2015
Biographie
Naissance
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Directeur de thèse
Distinction

Carrière universitaire

modifier

Reed obtient son doctorat (Ph.D.) en 1986 à McGill, sous la direction de Vašek Chvátal[2]. Avant de retourner à McGill pour une Chaire de Recherche du Canada, Reed a occupé des postes à l'Université de Waterloo, l'Université Carnegie-Mellon et au Centre national de la recherche scientifique[3].

Reed est élu membre (fellow) de la Société royale du Canada en 2009[4] et reçoit le Prix CRM-Fields-PIMS 2013 de l'Institut Fields[5].

Travaux

modifier

La thèse de recherche de Reed concerne les graphes parfaits[2]. Avec Michael Molloy, il est l'auteur d'un ouvrage sur la coloration de graphe et la méthode probabiliste[6]. Reed a également publié des articles souvent cités à propos du composant géant dans des graphes aléatoires avec un degré donné[7],[8], des problèmes de satisfaisabilité aléatoire[9], de l'acyclic coloring[10], la décomposition arborescente[11],[12] et versions constructives du lemme local de Lovász[13].

Sélection de publications

modifier

Articles

modifier
  • (en) Noga Alon, Bruce Reed et Colin McDiarmid, « Acyclic coloring of graphs », Random Structures & Algorithms, vol. 2, no 3,‎ , p. 277–288.
  • (en) Václav Chvátal et Bruce Reed, « Mick gets some (the odds are on his side) », Proc. 33rd Annual Symposium on Foundations of Computer Science,‎ , p. 620–627.
  • (en) Bruce A. Reed, « Finding approximate separators and computing tree width quickly », Proc. 24th Annual ACM Symposium on Theory of computing,‎ , p. 221–228.
  • (en) Michael Molloy et Bruce Reed, « A critical point for random graphs with a given degree sequence », Random Structures & Algorithms, vol. 6, nos 2-3,‎ , p. 161–179.
  • (en) Bruce Reed, « Tree width and tangles: a new connectivity measure and some applications », Surveys in combinatorics, 1997 (London),London Math. Soc. Lecture Note Ser., Cambridge Univ. Press, vol. 241,‎ , p. 87–162.
  • (en) Michael Molloy et Bruce Reed, « The size of the giant component of a random graph with a given degree sequence », Combinatorics, Probability and Computing, vol. 7, no 3,‎ 1998a, p. 295–305.
  • (en) Michael Molloy et Bruce Reed, « Further algorithmic aspects of the local lemma », Proc. 30th Annual ACM Symposium on Theory of computing,‎ 1998b, p. 524–529.

Ouvrages

modifier
  • Michael Molloy et Bruce Reed, Graph Colouring and the Probabilistic Method, vol. 23, Springer-Verlag "Algorithms and Combinatorics", (ISBN 3-540-42139-4).

Références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bruce Reed (mathematician) » (voir la liste des auteurs).

Notices

modifier

liens externes

modifier