Bruce Alan Reed FRSC es un matemático e informático canadiense , la Cátedra de Investigación de Canadá en Teoría de Gráficos y profesor de informática en la Universidad McGill . Su investigación se centra principalmente en la teoría de grafos . [1]
Carrera académica
Reed obtuvo su Ph.D. en 1986 de McGill, bajo la supervisión de Vašek Chvátal . [2] Antes de regresar a McGill como Cátedra de Investigación de Canadá, Reed ocupó cargos en la Universidad de Waterloo , la Universidad Carnegie Mellon y el Centro Nacional Francés de Investigación Científica . [3]
Reed fue elegido miembro de la Royal Society of Canada en 2009, [4] y recibió el premio CRM-Fields-PIMS 2013 . [5]
Investigar
La investigación de la tesis de Reed se refería a gráficos perfectos . [2] Junto a Michael Molloy, es autor de un libro sobre la coloración de gráficos y el método probabilístico . [6] Reed también ha publicado artículos muy citados sobre el componente gigante en gráficos aleatorios con una secuencia de grados determinada , [MR95] [MR98a] problemas de satisfacibilidad aleatorios , [CR92] coloración acíclica , [AMR91] descomposición de árboles , [R92] [R97 ] y versiones constructivas del lema local de Lovász . [MR98b]
Fue orador invitado en el Congreso Internacional de Matemáticos en 2002. [7] Su charla allí se refirió a una prueba de Reed y Benny Sudakov , utilizando el método probabilístico , de una conjetura de Kyoji Ohba que grafica cuyo número de vértices y número cromático son (asintóticamente) dentro de un factor de dos entre sí tienen el mismo número cromático y enumeran el número cromático . [RS02]
Publicaciones Seleccionadas
Artículos
AMR91. | Alon, Noga ; McDiarmid, Colin; Reed, Bruce (1991), "Coloración acíclica de gráficos", Estructuras y algoritmos aleatorios , 2 (3): 277–288, doi : 10.1002 / rsa.3240020303 , MR 1109695. |
CR92. | Chvátal, V .; Reed, B. (1992), "Mick obtiene algo (las probabilidades están de su lado)", Proc. 33º Simposio anual sobre los fundamentos de la informática , págs. 620–627, doi : 10.1109 / SFCS.1992.267789 , ISBN 978-0-8186-2900-6, S2CID 5575389. |
R92. | Reed, Bruce A. (1992), "Encontrar separadores aproximados y calcular el ancho del árbol rápidamente", Proc. 24º Simposio anual de ACM sobre teoría de la computación , págs. 221–228, doi : 10.1145 / 129712.129734 , ISBN 978-0897915113, S2CID 16259988. |
MR95. | Molloy, Michael; Reed, Bruce (1995), "Un punto crítico para gráficos aleatorios con una secuencia de grados dada", Estructuras y algoritmos aleatorios , 6 (2–3): 161–179, doi : 10.1002 / rsa.3240060204 , MR 1370952. |
R97. | Reed, BA (1997), "Ancho de árbol y enredos: una nueva medida de conectividad y algunas aplicaciones", Encuestas en combinatoria, 1997 (Londres) , London Math. Soc. Lecture Note Ser., 241 , Cambridge: Cambridge Univ. Prensa, págs. 87–162, doi : 10.1017 / CBO9780511662119.006 , ISBN 9780511662119, Señor 1477746. |
MR98a. | Molloy, Michael; Reed, Bruce (1998), "El tamaño del componente gigante de un gráfico aleatorio con una secuencia de grados dada", Combinatoria, Probabilidad y Computación , 7 (3): 295–305, doi : 10.1017 / S0963548398003526 , hdl : 1807 / 9487 , MR 1664335. |
MR98b. | Molloy, Michael; Reed, Bruce (1998), "Otros aspectos algorítmicos del lema local", Proc. 30º Simposio anual de ACM sobre teoría de la computación , págs. 524–529, doi : 10.1145 / 276698.276866 , hdl : 1807/9484 , ISBN 978-0897919623, S2CID 9446727. |
RS02. | Reed, Bruce; Sudakov, Benny (2002), "Coloración de listas de gráficos con como máximo (2 - o (1)) χ vértices", Actas del Congreso Internacional de Matemáticos, vol. III (Beijing, 2002) , Ed. Superior. Press, Beijing, págs. 587–603, arXiv : math / 0304467 , Bibcode : 2003math ...... 4467R , MR 1957563. |
Libros
MR02. | Molloy, Michael; Reed, Bruce (2002), Coloración de gráficos y método probabilístico , algoritmos y combinatorios, 23 , Berlín: Springer-Verlag, ISBN 978-3-540-42139-9. [8] |
Referencias
- ^ Presidentes: Bruce A. Reed , Cátedras de investigación de Canadá, consultado el 7 de octubre de 2012.
- ^ a b Bruce Reed en el Proyecto de genealogía de matemáticas
- ^ Miembros anteriores , Instituto Pacífico de Ciencias Matemáticas, consultado el 7 de octubre de 2012.
- ^ "Tres investigadores de McGill eligieron a RSC Fellows" , McGill Reporter , 1 de octubre de 2009
- ^ Bruce Reed anunciado como receptor del premio CRM / Fields / PIMS 2013, Pacific Institute for the Mathematical Sciences, consultado el 30 de diciembre de 2012.
- ^ Kayll, P. Mark (2003). Coloración gráfica y método probabilístico. Reseñas de Matemáticas , MR1869439 .
- ^ ICM Plenary and Invited Speakers since 1897 , International Mathematical Union , consultado el 1 de octubre de 2015.
- ^ Reseñas de coloración de gráficos y el método probabilístico :
- Fiamčik, Jozef, zbMATH , Zbl 0987.05002CS1 maint: publicación periódica sin título ( enlace )
- Kayll, P. Mark (2003), Revisiones matemáticas , MR 1869439CS1 maint: publicación periódica sin título ( enlace )
- Alon, Noga (marzo de 2003), SIAM Review , 45 (1): 131-132, JSTOR 25054375CS1 maint: publicación periódica sin título ( enlace )
enlaces externos
- Página de inicio
- Bruce A. Reed en el servidor de bibliografía DBLP
- Publicaciones de Bruce Reed indexadas por Google Scholar