Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, a former Canada Research Chair in Graph Theory at McGill University. [1] [2] His research is primarily in graph theory. [2] He is a distinguished research fellow of the Institute of Mathematics in the Academia Sinica, Taiwan, [3] and an adjunct professor at the University of Victoria in Canada. [4]
Reed earned his Ph.D. in 1986 from McGill, under the supervision of Vašek Chvátal. [5] 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. [6]
Reed was elected as a fellow of the Royal Society of Canada in 2009, [7] and is the recipient of the 2013 CRM-Fields-PIMS Prize. [8]
In 2021 he left McGill, and subsequently became a researcher at the Academia Sinica and an adjunct professor at the University of Victoria. [1] [3] [4]
Reed's thesis research concerned perfect graphs. [5] With Michael Molloy, he is the author of a book on graph coloring and the probabilistic method. [9] Reed has also published highly cited papers on the giant component in random graphs with a given degree sequence, [MR95] [MR98a] random satisfiability problems, [CR92] acyclic coloring, [AMR91] tree decomposition, [R92] [R97] and constructive versions of the Lovász local lemma. [MR98b]
He was an invited speaker at the International Congress of Mathematicians in 2002. [10] 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. [RS02]
| AMR91. | 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 . |
| CR92. | 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, ISBN 978-0-8186-2900-6, S2CID 5575389 . |
| R92. | 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 , ISBN 978-0897915113, S2CID 16259988 . |
| MR95. | 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 . |
| R97. | 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., vol. 241, Cambridge: Cambridge Univ. Press, pp. 87–162, doi:10.1017/CBO9780511662119.006, ISBN 9780511662119, MR 1477746 . |
| MR98a. | Molloy, Michael; Reed, Bruce (1998), "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, hdl: 1807/9487 , MR 1664335, S2CID 3712019 . |
| MR98b. | 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, hdl: 1807/9484 , ISBN 978-0897919623, S2CID 9446727 . |
| RS02. | Reed, Bruce; Sudakov, Benny (2002), "List colouring of graphs with at most (2 −o(1))χ vertices", 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 . |
| MR02. | Molloy, Michael; Reed, Bruce (2002), Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, vol. 23, Berlin: Springer-Verlag, ISBN 978-3-540-42139-9 . [11] |
{{citation}}: CS1 maint: untitled periodical (link){{citation}}: CS1 maint: untitled periodical (link){{citation}}: CS1 maint: untitled periodical (link)| International | |
|---|---|
| National | |
| Academics | |
| Other | |
