Glencora Borradaile

Assistant Professor

Computer Science

Web Page:

http://blogs.oregonstate.edu/glencora/

Learn more about Glencora Borradaile

Education:

Computer Science, Ph.D. December 2007
Brown University Providence, Rhode Island
Thesis: Exploiting planarity for network flow and connectivity problems.
Advisor: Philip Klein.
Computer Science, M.Sc. May 2004
Brown University Providence, Rhode Island
Mathematical and constraint programming.
Applied Mathematics, B.Sc. (Honours) April 2002
The University of Western Ontario London, Ontario
With a concentration in theoretical physics and fluid mechanics.

Biography:

Glencora Borradaile has a B.Sc. in Applied Mathematics from the University of Western Ontario (2002) and a Ph.D. in Computer Science from Brown University (2008). Before starting as faculty at Oregon State, she was a National Science and Engineering Research Council (NSERC) of Canada postdoctoral fellow in the Combinatorics and Optimization Department at the University of Waterloo.

Her research in algorithms started with traditional network flow and design problems in planar graphs. She still pursues these avenues, inspired by potential applications to problems in road networks, image processing and telecommunication networks. More generally she is interested in discrete optimization problems.

Research group:

AI - Machine Learning - Algorithms

Research Interests:

Research Areas
Theoretical computer science, algorithms, network algorithms, graph algorithms, discrete optimization, approximation algorithms

Teaching:

CS 523 ADVANCED ALGORITHMS

Publications

2011

Borradaile, G., P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen, "Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time", 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), Palm Springs, CA, IEEE, pp. 170 - 179, 10.2011. Abstract

2010

Borradaile, G., J. R. Lee, and A. Sidiropoulos, "Randomly Removing G Handles at Once", Computational Geometry, vol. 43, issue 8, pp. 655 - 662, 10/2010. Abstract

Borradaile, G., P. Sankowski, and C. Wulff-Nilsen, "Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time", CoRR, vol. abs/1003.1320, 2010.

2009

Borradaile, G., P. N. Klein, and C. Mathieu, "A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs", ACM Transactions on Algorithms, vol. 5, issue 3, pp. 1 - 31, 07/2009. Abstract

Borradaile, G., and P. N. Klein, "An O(n log n) Algorithm for Maximum St-Flow in a Directed Planar Graph", Journal of the ACM, vol. 56, issue 2, pp. 1 - 30, 04/2009. Abstract

Borradaile, G., E. D. Demaine, and S. Tazari, "Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs", 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), vol. 3, Dagstuhl, Germany, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 171–182, 02/2009. Abstract

2008

Borradaile, G., P. N. Klein, and C. Mathieu, "A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest", 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, IEEE, pp. 115 - 124, 10/2008. Abstract

Borradaile, G., and P. N. Klein, Lecture Notes in Computer ScienceAutomata, Languages and ProgrammingThe Two-Edge Connectivity Survivable Network Problem in Planar Graphs, , vol. 5125, Berlin, Heidelberg, Springer Berlin Heidelberg, pp. 485 - 501, 2008. Abstract

2005

Borradaile, G., and P. Van Hentenryck, "Safe and Tight Linear Estimators for Global Optimization", Mathematical Programming, vol. 102, issue 3, pp. 495 - 517, 01/2005. Abstract

School of Electrical Engineering & Computer Science