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

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

Брюс Алан Рид FRSC - канадский математик и ученый-компьютерщик , канадский исследовательский факультет теории графов и профессор информатики в Университете Макгилла . Его исследования в основном относятся к теории графов .

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

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

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

Исследовать

Исследования диссертации Рида касались идеальных графов . Вместе с Майклом Моллоем он является автором книги о раскраске графов и вероятностном методе . Рид также опубликовал широко цитируемые статьи о гигантской компоненте в случайных графах с заданной последовательностью степеней , проблемах случайной выполнимости , ациклической раскраске , древовидной декомпозиции и конструктивных версиях локальной леммы Ловаса .

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

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

Статьи

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

Книги

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

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

Внешние ссылки