Bruce Reed
# Bruce Reed

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.

## Carrière universitaire

Reed obtient son doctorat (Ph.D.) en 1986 à McGill, sous la direction de Vašek Chvátal. 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.

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

## Travaux

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

## Sélection de publications

### Articles

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

### Ouvrages

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