Anna Lubiw es una científica informática conocida por su trabajo en geometría computacional y teoría de grafos . Actualmente es profesora en la Universidad de Waterloo . [1]
Anna Lubiw | |
---|---|
Nacionalidad | canadiense |
alma mater | Universidad de Toronto |
Conocido por | Geometría computacional , teoría de grafos |
Esposos) | Jeffrey Shallit |
Premios | Miembro distinguido de ACM, 2009 |
Sitio web | https://cs.uwaterloo.ca/~alubiw/Site/Anna_Lubiw.html |
Educación
Lubiw recibió su doctorado en la Universidad de Toronto en 1986 bajo la supervisión conjunta de Rudolf Mathon y Stephen Cook . [2]
Investigar
En Waterloo, los estudiantes de Lubiw han incluido tanto a Erik Demaine como a su padre Martin Demaine , [3] con quien publicó la primera prueba del teorema de doblar y cortar en origami matemático . [4] En el dibujo de gráficos , Hutton y Lubiw encontraron un algoritmo de tiempo polinomial para el dibujo plano ascendente de gráficos con un único vértice fuente. [5] Otras contribuciones de Lubiw incluyen probar la NP-completitud de encontrar patrones de permutación , [6] y de encontrar alteraciones en grupos de permutación . [7]
Premios
Vida personal
Además de su trabajo académico, Lubiw es violinista aficionada [9] y preside el consejo de voluntarios a cargo de la orquesta de la Universidad de Waterloo. [10] Está casada con Jeffrey Shallit , también científico informático.
Publicaciones Seleccionadas
- Lubiw, Anna (1981), "Algunos problemas NP-completos similares al isomorfismo de grafos", SIAM Journal on Computing , 10 (1): 11-21, doi : 10.1137 / 0210002 , MR 0605600.
- Hutton, Michael D .; Lubiw, Anna (1996), "Dibujo plano hacia arriba de dígrafos acíclicos de fuente única", SIAM Journal on Computing , 25 (2): 291–311, doi : 10.1137 / S0097539792235906 , MR 1379303. Presentado por primera vez en el 2do Simposio ACM-SIAM sobre algoritmos discretos, 1991.
- Bose, Prosenjit ; Buss, Jonathan F .; Lubiw, Anna (1998), "Coincidencia de patrones para permutaciones", Cartas de procesamiento de información , 65 (5): 277–283, doi : 10.1016 / S0020-0190 (97) 00209-3 , MR 1620935. Presentado por primera vez en WADS 1993.
- Demaine, Erik D .; Demaine, Martin L .; Lubiw, Anna (1999), "Plegado y un corte recto es suficiente", Actas del Décimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA '99) , págs. 891–892.
Referencias
- ^ Perfil de la facultad Archivado el 22 de julio de 2013 en la Wayback Machine , Universidad de Waterloo, consultado el 16 de octubre de 2013.
- ^ Anna Lubiw en el Proyecto de genealogía matemática
- ^ "La estrella de las matemáticas desde fuera del redil" , Times Higher Education , 29 de marzo de 2002.
- ^ Demaine, Demaine y Lubiw (1999) ; O'Rourke, Joseph (2013), Cómo doblarlo , Cambridge University Press, pág. 144, ISBN 9781139498548.
- ^ Hutton y Lubiw (1996) ; Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998), "Prueba de planaridad ascendente óptima de dígrafos de fuente única", Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall , págs. 195-200, ISBN 978-0-13-301615-4.
- ^ Bose, Buss y Lubiw (1998) ; Brignall, Robert (2010), "Un estudio de permutaciones simples", en Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Permutation Patterns , London Mathematical Society Lecture Note Series, 376 , Cambridge University Press, págs. 41–66, ISBN 9781139488846, MR 2732823. Véanse en particular las págs. 61–62.
- ^ Lubiw (1981) ; Babai, László (1995), "Grupos de automorfismo, isomorfismo, reconstrucción", Manual de combinatoria, Vol. 1, 2 (PDF) , Amsterdam: Elsevier, págs. 1447-1540, MR 1373683 ,
Un resultado sorprendente de Anna Lubiw afirma que el siguiente problema es NP-completo: ¿Un grupo de permutación dado tiene un elemento libre de punto fijo?
. - ^ Página de miembro distinguido de ACM: http://awards.acm.org/award_winners/lubiw_2950848.cfm
- ^ "El amor por la música guía al conjunto novato", Kitchener Record , 29 de noviembre de 2005.
- ^ Acerca de la orquesta Archivado el 5 de junio de 2013 en Wayback Machine , Univ. of Waterloo, consultado el 16 de octubre de 2013.
enlaces externos
- Página de inicio en U. Waterloo
- Publicaciones de Anna Lubiw indexadas por Google Scholar