Anna Lubiw - Anna Lubiw

Anna Lubiw
Národnostkanadský
Alma materUniversity of Toronto
Známý jakoVýpočetní geometrie, teorie grafů
Manžel (y)Jeffrey Shallit
OceněníVýznamný člen ACM, 2009
webová stránkahttps://cs.uwaterloo.ca/~alubiw/Site/Anna_Lubiw.html

Anna Lubiw je počítačový vědec známá svou prací v výpočetní geometrie a teorie grafů. V současné době je profesorkou na University of Waterloo.[1]

Vzdělávání

Lubiw ji přijal Ph.D z University of Toronto v roce 1986 pod společným dohledem Rudolfa Mathona a Stephen Cook.[2]

Výzkum

Na Waterloo zahrnovali Lubiwovi studenti oba Erik Demaine a jeho otec Martin Demaine,[3] s nimiž zveřejnila první důkaz o skládací a rozřezaná věta v matematické origami.[4] v kreslení grafu, Hutton a Lubiw našli a polynomiální časový algoritmus pro nahoru rovinný výkres grafů s jediným zdrojovým vrcholem.[5] Mezi další příspěvky Lubiwa patří prokázání NP-úplnost nálezu permutační vzory,[6] a nálezu poruchy v permutační skupiny.[7]

Ocenění

Lubiw byl jmenován ACM Významný člen v roce 2009.[8]

Osobní život

Stejně jako její akademická práce je Lubiw amatérská houslistka,[9] a předsedá radě dobrovolníků odpovědné za orchestr University of Waterloo.[10] Je vdaná za Jeffrey Shallit, také počítačový vědec.

Vybrané publikace

  • Lubiw, Anna (1981), "Některé NP-úplné problémy podobné izomorfismu grafů", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, PAN  0605600.
  • Hutton, Michael D .; Lubiw, Anna (1996), "Nahoru planární kresba jednozdrojových acyklických digrafů", SIAM Journal on Computing, 25 (2): 291–311, doi:10.1137 / S0097539792235906, PAN  1379303. Poprvé představeno na 2. sympoziu ACM-SIAM o diskrétních algoritmech, 1991.
  • Bose, Prosenjit; Buss, Jonathan F .; Lubiw, Anna (1998), "Porovnávání vzorů pro permutace", Dopisy o zpracování informací, 65 (5): 277–283, doi:10.1016 / S0020-0190 (97) 00209-3, PAN  1620935. Poprvé představeno na WADS 1993.
  • Demaine, Erik D.; Demaine, Martin L.; Lubiw, Anna (1999), „Skládací a jeden rovný střih stačí“, Sborník z desátého výročního sympózia ACM-SIAM o diskrétních algoritmech (SODA '99), str. 891–892.

Reference

  1. ^ Profil fakulty Archivováno 2013-07-22 na Wayback Machine „University of Waterloo, vyvoláno 16. 10. 2013.
  2. ^ Anna Lubiw na Matematický genealogický projekt
  3. ^ „Matematická hvězda z vnějšku záhybu“, Times Higher Education, 29. března 2002.
  4. ^ Demaine, Demaine & Lubiw (1999); O'Rourke, Josephe (2013), Jak to složit, Cambridge University Press, str. 144, ISBN  9781139498548.
  5. ^ Hutton & Lubiw (1996); Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), „Optimální testování plošnosti jednostupňových digrafů směrem vzhůru“, Kreslení grafu: Algoritmy pro vizualizaci grafů, Prentice Hall, str. 195–200, ISBN  978-0-13-301615-4.
  6. ^ Bose, Buss & Lubiw (1998); Brignall, Robert (2010), „An survey of simple permutations“, in Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Permutační vzory, Série přednášek London Mathematical Society, 376, Cambridge University Press, s. 41–66, ISBN  9781139488846, PAN  2732823. Viz zejména s. 61–62.
  7. ^ Lubiw (1981); Babai, László (1995), „Automorfické skupiny, izomorfismus, rekonstrukce“, Handbook of combineatorics, Vol. 1, 2 (PDF), Amsterdam: Elsevier, s. 1447–1540, PAN  1373683, Překvapivý výsledek Anny Lubiw tvrdí, že následující problém je NP-úplný: Má daná permutační skupina prvek bez pevného bodu?.
  8. ^ Stránka ACM Distinguished Member: http://awards.acm.org/award_winners/lubiw_2950848.cfm
  9. ^ "Láska k hudebním průvodcům jako rodící se soubor", Kitchener Record, 29. listopadu 2005.
  10. ^ O orchestru Archivováno 06.06.2013 na Wayback Machine, Univ. Waterloo, vyvoláno 2013-10-16.

externí odkazy