Bruce Reed (mathematician)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Bruce Reed at the Bellairs Research Institute, 2015

Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, the Canada Research Chair in Graph Theory and a professor of computer science at McGill University.[1]

Academic career[edit]

Reed earned his Ph.D. in 1986 from McGill, under the supervision of Vašek Chvátal.[2] 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.[3]

Reed was elected as a fellow of the Royal Society of Canada in 2009,[4] and is the recipient of the 2013 CRM-Fields-PIMS Prize.[5]


Reed's thesis research concerned perfect graphs.[2] With Michael Molloy, he is the author of a book on graph coloring and the probabilistic method.[6] Reed has also published highly cited papers on the giant component in random graphs with a given degree sequence,[7] random satisfiability problems,[8] acyclic coloring,[9] tree decomposition,[10] and constructive versions of the Lovász local lemma.[11]

Selected publications[edit]


  • Alon, Noga; McDiarmid, Colin; Reed, Bruce (1991), "Acyclic coloring of graphs", Random Structures & Algorithms 2 (3): 277–288, doi:10.1002/rsa.3240020303, MR 1109695 .
  • Chvátal, V.; Reed, B. (1992), "Mick gets some (the odds are on his side)", Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 620–627, doi:10.1109/SFCS.1992.267789 .
  • 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 (1998a), "The size of the giant component of a random graph with a given degree sequence", Combinatorics, Probability and Computing 7 (3): 295–305, doi:10.1017/S0963548398003526, MR 1664335 .
  • Molloy, Michael; Reed, Bruce (1998b), "Further algorithmic aspects of the local lemma", Proc. 30th Annual ACM Symposium on Theory of computing, pp. 524–529, doi:10.1145/276698.276866 .


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


  1. ^ Chairholders: Bruce A. Reed, Canada Research Chairs, retrieved 2012-10-07.
  2. ^ a b Bruce Reed at the Mathematics Genealogy Project
  3. ^ Past members, Pacific Institute for the Mathematical Sciences, retrieved 2012-10-07.
  4. ^ "Three McGill researchers elected RSC Fellows", McGill Reporter, October 1, 2009 
  5. ^ Bruce Reed announced as 2013 CRM/Fields/PIMS Prize recipient , Pacific Institute for the Mathematical Sciences, retrieved 2012-12-30.
  6. ^ Kayll, P. Mark (2003). Graph Colouring and the Probabilistic Method. Mathematical Reviews, MR 1869439.
  7. ^ Molloy and Reed (1995, 1998a)
  8. ^ Chvátal & Reed (1992).
  9. ^ Alon, McDiarmid & Reed (1991).
  10. ^ Reed (1992, 1997).
  11. ^ Molloy & Reed (1998b).

External links[edit]