Bruce Reed

Bruce Reed (2015)

Bruce Allen Reed (* 1962) ist ein kanadischer Mathematiker und Informatiker, der sich mit Graphentheorie befasst.

Reed wurde 1986 an der McGill University bei Vašek Chvátal promoviert (A semi-strong perfect graph theorem). Er war an der University of Waterloo, der Carnegie Mellon University und forschte für das CNRS, bevor er Professor an der McGill University wurde, wo er einen Canada Research Chair für Graphentheorie innehat.

Er forschte über perfekte Graphen, Graphen-Minoren, Zufalls-Graphen, optimale Grafenfärbung unter Anwendung probabilistischer Methoden und Algorithmen zur Lösung von graphentheoretischen Problemen, die in Anwendungen wie Telefon-Netzwerken, VLSI-Design und dem World Wide Web anfallen.

2013 erhielt er den CRM-Fields-PIMS Prize. 2009 wurde er Fellow der Royal Society of Canada. 2002 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Peking (List colouring of graphs with at most $((2-o(1))\chi$ vertices, mit Benny Sudakov).

Schriften

• mit Michael Molloy: Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics 23, Berlin: Springer-Verlag 2002
• mit Noga Alon, Colin McDiarmid: Acyclic coloring of graphs, Random Structures & Algorithms, Band 2, 1991, S. 277–288
• mit V. Chvátal: Mick gets some (the odds are on his side), Proc. 33rd Annual Symposium on Foundations of Computer Science, 1992, S. 620–627.
• Finding approximate separators and computing tree width quickly, Proc. 24th Annual ACM Symposium on Theory of computing, 1992, S. 221–228.
• mit Michael Molloy: A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, Band 6, 1995, S. 161–179.
• 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, 1997, S. 87–162.
• mit M. Molloy: The size of the giant component of a random graph with a given degree sequence, Combinatorics, Probability and Computing, Band 7, 1998, S. 295–305.
• mit M. Molloy: Further algorithmic aspects of the local lemma, Proc. 30th Annual ACM Symposium on Theory of computing, 1998, S. 524–529.

Weblinks

• CRM-Fields-PIMS Preis für Reed