Anna Lubiw
chercheuse canadienne en informatique théorique
From Wikipedia, the free encyclopedia
Anna Lubiw est une chercheuse en informatique théorique et en mathématiques discrètes connue pour son travail dans le calcul de la géométrie et la théorie des graphes. Elle est actuellement professeur à l'Université de Waterloo.
Bell-Northern Research (en) (-
| Formation | |
|---|---|
| Activités | |
| Conjoint |
| A travaillé pour |
Université de Waterloo (depuis ) Bell-Northern Research (en) (- |
|---|---|
| Directeurs de thèse |
Rudolf Mathon (d), Stephen Cook |
| Distinction |
Biographie
Lubiw a reçu son BSc à l'Université de Toronto en 1979, son MSc à l'université de Waterloo en 1982, et son Ph. D de l'Université de Toronto en 1986, sous la supervision conjointe de Rudolf Mathon et Stephen Cook[1],[2].
À Waterloo, Lubiw les étudiants ont inclus à la fois Erik Demaine et son père Martin Demaine[3].
Elle est actuellement professeur à l'Université de Waterloo[4].
Recherche
Avec Martin Demaine elle a publié la première preuve de la fold-and-cut théorème en mathématiques de l'origami[5].
Dans le dessin de graphes, Hutton et Lubiw trouvé un algorithme polynomial en temps pour le problème du upward planar drawing (en) de graphes avec un unique sommet source[6].
Un autre travail remarquable est la preuve de NP-complétude du problème qui consiste à trouver des motifs de permutation[7], et des dérangements dans les groupes de permutations[8].
Récompenses
Vie personnelle
En plus de son travail universitaire, Lubiw est violoniste amateur[10], et préside le conseil des bénévoles s'occupant de l'orchestre de l'Université de Waterloo[11]. Elle est mariée à Jeffrey Shallit, également informaticien.
Sélection de publications
- (en) Anna Lubiw, « Some NP-complete problems similar to graph isomorphism », SIAM Journal on Computing, vol. 10, no 1, , p. 11–21 (DOI 10.1137/0210002, MR 605600).
- (en) Michael D. Hutton et Anna Lubiw, « Upward planar drawing of single-source acyclic digraphs », SIAM Journal on Computing, vol. 25, no 2, , p. 291–311 (DOI 10.1137/S0097539792235906, MR 1379303). D'abord présenté à la 2e ACM-SIAM Symposium sur les Algorithmes Discrets, 1991.
- (en) Prosenjit Bose, Jonathan F. Buss et Anna Lubiw, « Pattern matching for permutations », Information Processing Letters, vol. 65, no 5, , p. 277–283 (DOI 10.1016/S0020-0190(97)00209-3, MR 1620935). D'abord présenté à WAD 1993.
- (en) Erik D. Demaine, Martin L. Demaine et Anna Lubiw, « Folding and one straight cut suffice », Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '99), , p. 891–892 (lire en ligne).
