Publications

Min st-cut oracle for planar graphs with near-linear preprocessing time

Glencora Borradaile and Christian Wulff-Nilsen
arXiv, March, 2010.

Randomly removing g handles at once

Glencora Borradaile, James Lee and Anastasios Sidiropoulos
Computational Geometry: Theory and Applications special issue for SoCG’09.

Approximation algorithms for constrained knapsack problems

Glencora Borradaile, Brent Heeringa, Gordon Wilfong
arXiv, October, 2009.

A polynomial-time approximation scheme for Steiner tree in planar graphs

Glencora Borradaile, Philip Klein and Claire Mathieu
ACM Transactions on Algorithms (special issue for SODA 2007), 5(3), 2009.

Randomly removing g handles at once

Glencora Borradaile, James Lee and Anastasios Sidiropoulos
Proceedings of the Annual Symposium on Computational Geometry (SoCG), Aarhus, Denmark, 2009.

An O(n log n) algorithm for maximum st-flow in a directed planar graph

Glencora Borradaile and Philip Klein
Journal of the ACM, 56(2), 2009.

Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs

Glencora Borradaile, Erik Demaine and Siamak Tazari
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany, 2009.

A polynomial-time approximation scheme for Euclidean Steiner forest

Glencora Borradaile, Philip Klein and Claire Mathieu
Symposium of Foundations of Computer Science (FOCS), Philadelphia, Pennsylvania, 2008.

The two-edge connectivity survivable network problem in planar graphs

Glencora Borradaile and Philip Klein
Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP) Reykjavik, Iceland, 2008.

Planarity testing

Glencora Borradaile
Encyclopedia of Algorithms, invited entry, 2008.

Exploiting Planarity for Network Flow and Connectivity Problems

Glencora Borradaile
Doctoral Dissertation, Brown University, 2007.

Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon

Glencora Borradaile, Philip Klein and Claire Mathieu
Proceedings of the Workshop on Algorithms and Data Structures (WADS), Halifax, Nova Scotia, 2007.

A polynomial-time approximation scheme for Steiner tree in planar graphs

Glencora Borradaile, Claire Kenyon-Mathieu and Philip Klein
Proceedings of the Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana, 2007.

An O(n log n) algorithm for maximum st-flow in a directed planar graph

Glencora Borradaile and Philip Klein
Proceedings of the Symposium of Discrete Algorithms (SODA), Miami, Florida, 2006.

Safe and tight linear estimators for global optimization

Glencora Borradaile and Pascal Van Hentenryck
Mathematical Programming, 102(3), 2005.