Bruce Reed

Bruce Reed à l'Institut de Recherche de Bellairs en 2015

Biographie
Naissance	1962
Nationalité	canadienne
Formation	Université McGill
Activités	Mathématicien, informaticien

Autres informations
A travaillé pour	Université McGill Université Carnegie-Mellon Université de Waterloo
Directeur de thèse	Václav Chvátal
Distinction	Prix CRM-Fields-PIMS (2013)

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].

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].

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].

(en) Noga Alon, Bruce Reed et Colin McDiarmid, « Acyclic coloring of graphs », Random Structures & Algorithms, vol. 2, n^o 3,‎ 1991, 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,‎ 1992, p. 620–627.
(en) Bruce A. Reed, « Finding approximate separators and computing tree width quickly », Proc. 24th Annual ACM Symposium on Theory of computing,‎ 1992, 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, n^os 2-3,‎ 1995, 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,‎ 1997, 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, n^o 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.

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

(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).