Любив, Анна
| Анна Любив | |
|---|---|
| англ. Anna Lubiw | |
| Страна | Канада |
| Род деятельности | специалист в области информатики, преподаватель университета |
| Место работы | Университет Уотерлу |
| Альма-матер | Университет Торонто |
| Учёная степень | Ph.D |
| Научный руководитель | Рудольф Матон, Стивен Кук |
| Ученики | Эрик Демейн |
| Известна как | автор работ в вычислительной геометрии и теории графов |
| Награды и премии | выдающийся член ACM, 2009 |
| Сайт | cs.uwaterloo.ca/~alubiw/… |
Анна Любив — информатик, известная своими работами в вычислительной геометрии и теории графов. В настоящее время является профессором университета Уотерлу[1].
Образование
Любив получила степень Ph.D в университете Торонто в 1986 под совместным руководством Рудольфа Матона и Стивена Кука[2].
Исследования
В Уотерлу среди учеников Любив были Эрик Демейн и его отец Мартин Демейн[3], с которыми она опубликовала первое доказательство теоремы о складывании и отрезании в математике оригами[4][5].
В визуализации графов Хаттон и Любив нашли алгоритм с полиномиальным временем для восходящего планарного представления графов с одной исходной вершиной[6] [7]
Среди других работ Любив доказательство NP-полноты поиска схем перестановок[8][9]. и поиск беспорядков в группах перестановок[10][11].
Награды
Любив была признана в 2009 году выдающимся членом ACM[12].
Личная жизнь
Кроме академической работы Любив является виолончелистсткой-любительницей[13] и возглавляет волонтёрский совет оркестра Университета Уотерлу[14]. Любив замужем за Джеффри Шаллит, который также является информатиком.
Избранные публикации
- Anna Lubiw. Some NP-complete problems similar to graph isomorphism // SIAM Journal on Computing. — 1981. — Т. 10, вып. 1. — С. 11–21. — doi:10.1137/0210002.
- Michael D. Hutton, Anna Lubiw. Upward planar drawing of single-source acyclic digraphs // SIAM Journal on Computing. — 1996. — Т. 25, вып. 2. — С. 291–311. — doi:10.1137/S0097539792235906.. First presented at the 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
- Prosenjit Bose, Jonathan F. Buss, Anna Lubiw. Pattern matching for permutations // Information Processing Letters. — 1998. — Т. 65, вып. 5. — С. 277–283. — doi:10.1016/S0020-0190(97)00209-3.. First presented at WADS 1993.
- Erik D. Demaine, Martin L. Demaine, Anna Lubiw. Folding and one straight cut suffice // Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '99). — 1999. — С. 891–892.
Примечания
- ↑ Faculty profile Архивировано 22 июля 2013 года., University of Waterloo, retrieved 2013-10-16.
- ↑ Любив, Анна (англ.) в проекте «Математическая генеалогия»
- ↑ Maths star from outside the fold // Times Higher Education. — 2002. — 29 апреля.
- ↑ Demaine, Demaine, Lubiw, 1999, с. 891–892.
- ↑ O'Rourke, 2013, с. 144.
- ↑ Hutton, Lubiw, 1996, с. 195–200.
- ↑ Di Battista, Eades, Tamassia, Tollis, 1998, с. 195–200.
- ↑ Bose, Buss, Lubiw, 1998, с. 277–283.
- ↑ Brignall, 2010, с. 41–66.
- ↑ Lubiw, 1981, с. 1447–1540.
- ↑ Babai, 1995, с. 1447–1540.
- ↑ ACM Distinguished member page: http://awards.acm.org/award_winners/lubiw_2950848.cfm
- ↑ Love of music guides fledgling ensemble // Kitchener Record. — 2005. — 29 ноября.
- ↑ About the orchestra Архивировано 5 июня 2013 года., Univ. of Waterloo, retrieved 2013-10-16.
Литература
- Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Optimal Upward Planarity Testing of Single-Source Digraphs // Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — С. 195–200. — ISBN 978-0-13-301615-4.
- Joseph O'Rourke. How to Fold It. — Cambridge University Press, 2013. — С. 144. — ISBN 9781139498548.
- Robert Brignall. A survey of simple permutations // Permutation Patterns / ed. Steve Linton, Nik Ruškuc, Vincent Vatter. — Cambridge University Press, 2010. — Т. 376. — С. 41–66. — (London Mathematical Society Lecture Note Series). — ISBN 9781139488846. См., в частности, стр. 61–62
- László Babai. Automorphism groups, isomorphism, reconstruction // Handbook of combinatorics, Vol. 1, 2. — Amsterdam: Elsevier, 1995. — С. 1447–1540. Цитата: "A surprising result of Anna Lubiw asserts that the following problem is NP-complete: Does a given permutation group have a fixed-point-free element?"