Bruce Alan Reed is a FRSC Canadian mathematician and computer scientist, the Canada Research Chair in Graph Theory and a professor of computer science at McGill University. His research is primarily in graph theory.
Academic career [ edit ]
Reed earned his Ph.D. in 1986 from McGill, under the supervision of
Vašek Chvátal. Before returning to McGill as a Canada Research Chair, Reed held positions at the  University of Waterloo, Carnegie Mellon University, and the French National Centre for Scientific Research.
Reed was elected as a fellow of the
Royal Society of Canada in 2009, and is the recipient of the 2013  CRM-Fields-PIMS Prize.
Research [ edit ]
Reed's thesis research concerned
With Michael Molloy, he is the author of a book on  graph coloring and the probabilistic method. Reed has also published highly cited papers on the  giant component in random graphs with a given degree sequence, [MR95] random [MR98a] satisfiability problems, [CR92] acyclic coloring, [AMR91] tree decomposition, [R92] and constructive versions of the [R97] Lovász local lemma.
He was an
invited speaker at the International Congress of Mathematicians in 2002. His talk there concerned a proof by Reed and  Benny Sudakov, using the probabilistic method, of a conjecture by Kyoji Ohba that graphs whose number of vertices and chromatic number are (asymptotically) within a factor of two of each other have equal chromatic number and list chromatic number.
Selected publications [ edit ]
Articles [ edit ]
Reed, Bruce A. (1992), "Finding approximate separators and computing tree width quickly", Proc. 24th Annual ACM Symposium on Theory of computing, pp. 221–228, doi: 10.1145/129712.129734 .
Molloy, Michael; Reed, Bruce (1995), "A critical point for random graphs with a given degree sequence", Random Structures & Algorithms, 6 (2–3): 161–179, doi: 10.1002/rsa.3240060204, MR 1370952 .
Reed, B. A. (1997), "Tree width and tangles: a new connectivity measure and some applications", Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., 241, Cambridge: Cambridge Univ. Press, pp. 87–162, doi: 10.1017/CBO9780511662119.006, MR 1477746 .
Molloy, Michael; Reed, Bruce (1998), "Further algorithmic aspects of the local lemma", Proc. 30th Annual ACM Symposium on Theory of computing, pp. 524–529, doi: 10.1145/276698.276866 .
Reed, Bruce; Sudakov, Benny (2002), "List colouring of graphs with at most (2 − vertices", o(1)) χ Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), Higher Ed. Press, Beijing, pp. 587–603, arXiv: , math/0304467 Bibcode: 2003math......4467R, MR 1957563 .
Molloy, Michael; Reed, Bruce (2002), Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, 23, Berlin: Springer-Verlag, ISBN 3-540-42139-4, MR 1869439 .
References [ edit ]
Chairholders: Bruce A. Reed, Canada Research Chairs, retrieved 2012-10-07.
^ a b
Bruce Reed at the Mathematics Genealogy Project
Past members, Pacific Institute for the Mathematical Sciences, retrieved 2012-10-07.
"Three McGill researchers elected RSC Fellows", McGill Reporter, October 1, 2009
Bruce Reed announced as 2013 CRM/Fields/PIMS Prize recipient , Pacific Institute for the Mathematical Sciences, retrieved 2012-12-30.
^ Kayll, P. Mark (2003). Graph Colouring and the Probabilistic Method.
Mathematical Reviews, MR 1869439.
, ICM Plenary and Invited Speakers since 1897 International Mathematical Union , retrieved 2015-10-01 .
External links [ edit ]