Брюс Рид (математик) - Bruce Reed (mathematician) - Wikipedia

Брюс Рид в Исследовательский институт Беллэрса, 2015

Брюс Алан Рид FRSC это Канадский математик и специалист в области информатики, то Кафедра исследований Канады кандидат теории графов и профессор компьютерных наук в Университет Макгилла. Его исследования в основном теория графов.[1]

Академическая карьера

Рид получил докторскую степень. в 1986 году из МакГилла под руководством Вашек Хватал.[2] Перед тем, как вернуться в МакГилл в качестве руководителя исследований в Канаде, Рид занимал должности в Университет Ватерлоо, Университет Карнеги Меллон, а Французский национальный центр научных исследований.[3]

Рид был избран членом Королевское общество Канады в 2009,[4] и является лауреатом премии 2013 г. CRM-Fields-PIMS Приз.[5]

Исследование

Исследование диссертации Рида касалось идеальные графики.[2]Вместе с Майклом Моллоем он является автором книги о раскраска графика и вероятностный метод.[6] Рид также опубликовал высоко цитируемые статьи о гигантский компонент в случайные графы с данным последовательность степеней,[MR95][MR98a] случайный проблемы выполнимости,[CR92] ациклическая окраска,[AMR91] разложение дерева,[R92][R97] и конструктивные варианты Локальная лемма Ловаса.[MR98b]

Он был приглашенный спикер Международного конгресса математиков в 2002.[7] Его выступление касалось доказательства Рида и Бенни Судаков, с использованием вероятностный метод, гипотезы Кёдзи Охбы, что графы с числом вершин и хроматическое число (асимптотически) с точностью до двух раз имеют одинаковое хроматическое число и список хроматических чисел.[RS02]

Избранные публикации

Статьи

AMR91.Алон, Нога; МакДиармид, Колин; Рид, Брюс (1991), "Ациклическая раскраска графов", Случайные структуры и алгоритмы, 2 (3): 277–288, Дои:10.1002 / RSA.3240020303, МИСТЕР  1109695.
CR92.Хватал, В.; Рид, Б. (1992), «Мик получает немного (шансы на его стороне)», Proc. 33-й ежегодный симпозиум по основам компьютерных наук, стр. 620–627, Дои:10.1109 / SFCS.1992.267789, ISBN  978-0-8186-2900-6, S2CID  5575389.
R92.Рид, Брюс А. (1992), «Нахождение приблизительных разделителей и быстрое вычисление ширины дерева», Proc. 24-й ежегодный симпозиум ACM по теории вычислений, стр. 221–228, Дои:10.1145/129712.129734, ISBN  978-0897915113, S2CID  16259988.
MR95.Моллой, Майкл; Рид, Брюс (1995), "Критическая точка для случайных графов с заданной последовательностью степеней", Случайные структуры и алгоритмы, 6 (2–3): 161–179, Дои:10.1002 / RSA.3240060204, МИСТЕР  1370952.
R97.Рид, Б. А. (1997), "Ширина дерева и путаница: новая мера связности и некоторые приложения", Обзоры по комбинаторике, 1997 г. (Лондон), Лондонская математика. Soc. Lecture Note Ser., 241, Кембридж: Cambridge Univ. Press, стр. 87–162, Дои:10.1017 / CBO9780511662119.006, ISBN  9780511662119, МИСТЕР  1477746.
MR98a.Моллой, Майкл; Рид, Брюс (1998), «Размер гигантского компонента случайного графа с заданной последовательностью степеней», Комбинаторика, теория вероятностей и вычисления, 7 (3): 295–305, Дои:10.1017 / S0963548398003526, HDL:1807/9487, МИСТЕР  1664335.
MR98b.Моллой, Майкл; Рид, Брюс (1998), "Дальнейшие алгоритмические аспекты локальной леммы", Proc. 30-й ежегодный симпозиум ACM по теории вычислений, стр. 524–529, Дои:10.1145/276698.276866, HDL:1807/9484, ISBN  978-0897919623, S2CID  9446727.
RS02.Рид, Брюс; Судаков, Бенни (2002), "Раскраска списком графов с не более чем (2 − о(1))χ вершины ", Труды Международного конгресса математиков, Vol. III (Пекин, 2002 г.), Высшее изд. Press, Пекин, стр. 587–603, arXiv:математика / 0304467, Bibcode:2003математика ...... 4467R, МИСТЕР  1957563.

Книги

MR02.Моллой, Майкл; Рид, Брюс (2002), Раскраска графа и вероятностный метод., Алгоритмы и комбинаторика, 23, Берлин: Springer-Verlag, ISBN  978-3-540-42139-9.[8]

Рекомендации

  1. ^ Председатели: Брюс А. Рид, Canada Research Chairs, получено 07.10.2012.
  2. ^ а б Брюс Рид на Проект "Математическая генеалогия"
  3. ^ Прошлые участники, Тихоокеанский институт математических наук, дата обращения 07.10.2012.
  4. ^ «Трое исследователей McGill избраны стипендиатами RSC», McGill Reporter, 1 октября 2009 г.
  5. ^ Брюс Рид объявлен лауреатом премии CRM / Fields / PIMS 2013, Тихоокеанский институт математических наук, дата обращения 30 декабря 2012.
  6. ^ Кайл, П. Марк (2003). Раскраска графов и вероятностный метод. Математические обзоры, МИСТЕР1869439.
  7. ^ Пленарное заседание ICM и приглашенные спикеры с 1897 г., Международный математический союз, получено 2015-10-01.
  8. ^ Обзоры Раскраска графа и вероятностный метод.:
    • Фиамчик, Юзеф, zbMATH, Zbl  0987.05002CS1 maint: журнал без названия (связь)
    • Кайл, П. Марк (2003), Математические обзоры, МИСТЕР  1869439CS1 maint: журнал без названия (связь)
    • Алон, Нога (Март 2003 г.), SIAM Обзор, 45 (1): 131–132, JSTOR  25054375CS1 maint: журнал без названия (связь)

внешняя ссылка