Glencora Borradaile






         Associate Professor & College of Engineering Dean's Professor, School of Electrical Engineering and Computer Science, Oregon State University

Publications

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs
* Entry in the Encyclopedia of Algorithms, 2nd Edition, edited by Ming-Yang Kao. 2008.
[ pdf ]

Maximum st-Flow in Planar Graphs
* Entry in the Encyclopedia of Algorithms, 2nd Edition, edited by Ming-Yang Kao. 2008.
[ pdf ]

All-pairs minimum cuts in near-linear time for surface-embedded graphs
Glencora Borradaile, David Eppstein, Amir Nayyeri and Christian Wulff-Nilsen
* SoCG 2016
[ arXiv ]

Minimum cycle and homology bases of surface embedded graphs
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox and Amir Nayyeri
* SoCG 2016

Towards single face shortest vertex-disjoint paths in undirected planar graphs
Glencora Borradaile, Amir Nayyeri and Farzad Zafarani
* ESA 2015
[ arXiv ]

Optimal dynamic program for r-domination problems over tree decompositions
Glencora Borradaile and Hung Le
* preprint, 2015
[ arXiv ]

Improving robustness of next-hop routing
Glencora Borradaile, W. Sean Kennedy, Gordon Wilfong and Lisa Zhang
* Journal of Combinatorial Optimization, pp. 1-15, doi 10.1007/s10878-014-9818-x December 2014.
[ arXiv ]

Planar induced subgraphs of sparse graphs
Glencora Borradaile, David Eppstein and Pingan Zhu
* Journal of Graph Algorithms and Applications, Vol. 19, no. 1, pp. 281-297, 2015.
* Graph Drawing 2014
[ arXiv ]

Density decompositions of networks
Theresa Migler, Glencora Borradaile and Gordon Wilfong
* preprint, 2014
[ arXiv ] [ accompanying source code ]

Covering nearly surface-embedded graphs with a fixed number of balls
Glencora Borradaile and Erin Wolf Chambers
* Discrete & Computational Geometry, pp. 979-996, volume 54, issue 4, 2014.
[ arXiv ]

A polynomial-time approximation scheme for Euclidean Steiner forest.
Glencora Borradaile, Philip Klein and Claire Mathieu.
* Transactions on Algorithms, Volume 11, Issue 3, Article 19, January 2015.
* Foundations of Computer Science (FOCS), 2008.
[ arXiv ]

Algorithms for Optimization Problems in Planar Graphs
Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu.
* Dagstuhl Reports, pp. 35–57, volume 3, number 10, 2014.
[ doi ]

Min st-cut oracle for planar graphs with near-linear preprocessing time.
Glencora Borradaile, Piotr Sankowski and Christian Wulff-Nilsen.
* Transactions on Algorithms, Volume 11, Issue 3, Article 16, January 2015.
* Foundations of Computer Science (FOCS), 2010.
[ arXiv ]

Maximum st-flow in directed planar graphs via shortest paths.
Glencora Borradaile and Anna Harutyunyan.
* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
[ arXiv ]

Boundary-to-boundary flows in planar graphs.
Glencora Borradaile and Anna Harutyunyan.
* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
[ arXiv ]

Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, Lisa Zhang
preprint, 2013
[ arXiv ]

Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets
Glencora Borradaile and David Eppstein.
* Canadian Conference on Computational Geometry (CCCG), 2012.
* To appear in Computational Geometry: Theory and Applications special issue for CCCG 2012.
[ arXiv ]

Connectivity oracles for planar graphs
Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen.
* Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.
arXiv ]

Planted-model evaluation of algorithms for identifying differences between spreadsheets
Anna Harutyunyan, Glencora Borradaile, Christopher Chambers and Christopher Scaffidi.
* IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), 2012.
[ pdf ]

Batch active learning via coordinating  matching
Javad Azimi, Alan Fern, Xiaoli Fern, Glencora Borradaile, and Brent Heeringa.
* International Conference on Machine Learning (ICML), 2012.
[ arXiv ]

Approximation algorithms for constrained knapsack problems
Glencora Borradaile, Brent Heeringa and Gordon Wilfong.
* Journal of Discrete Algorithms special issue for IWOCA 2011, 2012.
* International Workshop on Combinatorial Algorithms (IWOCA), 2011.
arXiv ]

Polynomial-time approximation schemes for connectivity problems in bounded-genus graphs.
Glencora Borradaile, Erik Demaine and Siamak Tazari.
* Algorithmica, 2012.
* Int’l Symp. on Theoretical Aspects of Computer Science (STACS), 2009.
[ arXiv ]

Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
Glencora Borradaile, Philip Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen.
* Foundations of Computer Science (FOCS), 2011.
[ arXiv ]

Multiple source, single sink maximum flow in a planar graph
Glencora Borradaile and Christian Wulff-Nilsen.
* Manuscript, 2010.
[ arXiv ]

Randomly removing g handles at once.
Glencora Borradaile, James Lee and Anastasios Sidiropoulos.
* Computational Geometry: Theory and Applications special issue for SoCG 2009, volume 43, 2010.
* Symposium on Computational Geometry (SoCG), 2009.
[ arXiv ]

A polynomial-time approximation scheme for Steiner tree in planar graphs.
Glencora Borradaile, Claire Mathieu, and Philip Klein.
* ACM Transactions on Algorithms special issue for SODA 2007, 5(3), 2009.
* Symposium on Discrete Algorithms (SODA), 2007.
[ pdf, full version ]

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.
* Symposium on Discrete Algorithms (SODA), 2006.
[ pdf, full version ]

The two-edge connectivity survivable network problem in planar graphs.
Glencora Borradaile and Philip Klein.
* Int’l Colloq. on Automata, Languages and Programming (ICALP), 2008.
[ arXiv, full version, in journal submission ]

Planarity Testing
* Entry in the Encyclopedia of Algorithms, edited by Ming-Yang Kao. 2008.
pdf ]

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.
* Workshop of Algorithms and Data Structures (WADS), 2007.
[ incorporated into journal version listed above ]

Safe and tight linear estimators for global optimization.
Glencora Borradaile and Pascal Van Hentenryck.
* Mathematical Programming, 102(3), 2005.
[ pdf ]

Exploiting Planarity for Network Flow and Connectivity Problems
Glencora Borradaile.
Dissertation, Brown University, December 2007.
[ pdf ]

Print Friendly

© 2016 Glencora Borradaile   Powered by WordPress MU    Hosted by blogs.oregonstate.edu