Bruce Alan ReedFRSC is aCanadianmathematician andcomputer scientist, a formerCanada Research Chair in Graph Theory atMcGill University.[1][2] His research is primarily ingraph theory.[2] He is a distinguished research fellow of the Institute of Mathematics in theAcademia Sinica, Taiwan,[3] and an adjunct professor at theUniversity of Victoria in Canada.[4]
Reed earned his Ph.D. in 1986 from McGill, under the supervision ofVašek Chvátal.[5] Before returning to McGill as a Canada Research Chair, Reed held positions at theUniversity of Waterloo,Carnegie Mellon University, and theFrench National Centre for Scientific Research.[6]
Reed was elected as a fellow of theRoyal Society of Canada in 2009,[7] and is the recipient of the 2013CRM-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 concernedperfect graphs.[5]With Michael Molloy, he is the author of a book ongraph coloring and theprobabilistic method.[9] Reed has also published highly cited papers on thegiant component inrandom graphs with a givendegree sequence,[MR95][MR98a] randomsatisfiability problems,[CR92]acyclic coloring,[AMR91]tree decomposition,[R92][R97] and constructive versions of theLovász local lemma.[MR98b]
He was aninvited speaker at the International Congress of Mathematicians in 2002.[10] His talk there concerned a proof by Reed andBenny Sudakov, using theprobabilistic method, of a conjecture by Kyoji Ohba that graphs whose number of vertices andchromatic number are (asymptotically) within a factor of two of each other have equal chromatic number andlist 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)