{"id":780,"date":"2012-01-27T23:33:52","date_gmt":"2012-01-27T23:33:52","guid":{"rendered":"http:\/\/blogs.oregonstate.edu\/glencora\/?page_id=780"},"modified":"2021-10-21T17:33:37","modified_gmt":"2021-10-21T17:33:37","slug":"publications","status":"publish","type":"page","link":"https:\/\/blogs.oregonstate.edu\/glencora\/publications\/","title":{"rendered":"Publications"},"content":{"rendered":"

\"\"<\/p>\n

Publications by my students while they were studying with me that I did not co-author are below<\/a>.<\/p>\n

Defend Dissent: Digital Suppression and Cryptographic Defense of Social Movements<\/strong>
\nGlencora Borradaile
\n* Open Textbook @ OSU<\/a>, 2021<\/p>\n

The Motivated Can Encrypt (Even with PGP)<\/strong>
\nGlencora Borradaile, Kelsy Kretschmer, Michele Gretes, Alexandria LeClerc
\n* PETS 2021
\n[ arXiv<\/a> ]<\/p>\n

Listen up, STEM: We Don’t Just Teach Facts
\n<\/strong>Glencora Borradaile
\n* Chapter in Transformative Approaches to Social Justice Education, <\/em>Routledge 2021
\n[ last unproofed version<\/a> ]<\/p>\n

Sousveillance Capitalism
\n<\/strong>Glencora Borradaile, Joshua Reeves
\n* Surveillance and Society 2020
\n[ doi<\/a> ]
\n<\/strong><\/p>\n

Low-stretch spanning trees of graphs with bounded width
\n<\/strong>Glencora Borradaile, Erin Chambers, David Eppstein, Will Maxwell, Amir Nayyeri
\n* SWAT 2020
\n[ arXiv<\/a> ] [ summary by David Eppstein<\/a> ]<\/p>\n

Minimum bounded chains and minimum homologous chains in
\nembedded simplicial complexes
\n<\/strong>Glencora Borradaile, Will Maxwell, Amir Nayyeri
\n* SoCG 2020
\n[ arXiv<\/a> ]<\/p>\n

Whose Tweets are <\/strong>Surveilled for the Police: An Audit of a Social-Media Monitoring Tool via Log Files
\n<\/strong>Glencora Borradaile, Brett Burkhardt, Alexandria LeClerc
\n* FAT* 2020 (now FAccT)
\n[ arXiv<\/a> ][ lay summary<\/a> ]<\/p>\n

Greedy spanners are optimal in doubling metrics<\/strong>
\nGlencora Borradaile, Hung Le, Christian Wulff-Nilsen
\n* SODA 2019
\n[ arXiv<\/a> ]<\/p>\n

Designing practical PTASes for minimum feedback vertex set in planar graphs<\/strong>
\nGlencora Borradaile, Hung Le, Baigong Zheng
\n* SEA 2019
\n[ arXiv<\/a> ]<\/p>\n

Training the Motivated: Digital Security for Activists<\/strong>
\nGlencora Borradaile and Kelsy Kretschmer
\n* SOUPS’17
\n[ USENIX<\/a> ]<\/p>\n

Density decompositions of networks<\/strong>
\nTheresa Migler, Glencora Borradaile and Gordon Wilfong
\n* CompleNet’18
\n[ arXiv<\/a> ] [ accompanying source code<\/a> ]<\/p>\n

Minor-free graphs have light spanners<\/strong>
\nGlencora Borradaile, Hung Le, Christian Wulff-Nilsen
\n* FOCS 2017.
\n[ arXiv<\/a> ]<\/p>\n

Large induced acyclic and outerplanar subgraphs of 2-outerplanar graphs
\n<\/strong>Glencora Borradaile, Hung Le, Melissa Sherman-Bennett
\n* Graphs and Combinatorics, 2017
\n[ arXiv<\/a> ]<\/p>\n

A PTAS for three-edge connectivity in planar graphs
\n<\/strong>Glencora Borradaile, Baigong Zheng
\n* APPROX 2017
\n[ arXiv<\/a> ]<\/p>\n

Egalitarian Graph Orientations<\/strong>
\nGlencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, Lisa Zhang
\n* Journal of Graph Algorithms and Applications, Vol. 21, no. 4, 2017
\n[ arXiv<\/a> ]<\/p>\n

Light spanners for bounded treewidth graphs imply light spanners for H-minor-free graphs<\/strong>
\nGlencora Borradaile, Hung Le
\n[ arXiv<\/a> ]<\/p>\n

Embedded-width: A variant of treewidth for plane graphs<\/strong>
\nGlencora Borradaile, Jeff Erickson, Hung Le, Robbie Weber
\n[ arXiv<\/a> ]<\/p>\n

Minimum cycle and homology bases of surface embedded graphs<\/strong>
\nGlencora Borradaile, Erin Wolf Chambers, Kyle Fox and Amir Nayyeri
\n* SoCG 2016
\n* JoCG 2017, special issue for SoCG 2016
\n[ arXiv<\/a> ]<\/p>\n

Optimal dynamic program for r-domination problems over tree decompositions.
\n<\/strong>Glencora Borradaile and Hung Le.
\n<\/strong>* International Symposium on Parameterized and Exact Computation (IPEC), 2016.
\n[ arXiv<\/a> ]<\/p>\n

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs<\/strong>
\n* Entry in the Encyclopedia of Algorithms<\/a>, 2nd Edition, edited by Ming-Yang Kao. 2016.
\n[ pdf<\/a> ]<\/p>\n

Maximum st-Flow in Planar Graphs
\n<\/strong>* Entry in the Encyclopedia of Algorithms<\/a>, 2nd Edition, edited by Ming-Yang Kao. 2016.
\n[ pdf<\/a> ]<\/p>\n

All-pairs minimum cuts in near-linear time for surface-embedded graphs
\n<\/strong>Glencora Borradaile, David Eppstein, Amir Nayyeri and Christian Wulff-Nilsen
\n* SoCG 2016
\n[ arXiv<\/a> ]<\/p>\n

The two-edge connectivity survivable network problem in planar graphs.<\/strong>
\nGlencora Borradaile and Philip Klein.
\n* Transactions on Algorithms, Volume 12, Issue 3, June 2016
\n* Int\u2019l Colloq. on Automata, Languages and Programming (ICALP), 2008.
\n[ arXiv<\/a> ]<\/p>\n

Towards single face shortest vertex-disjoint paths in undirected planar graphs
\n<\/strong>Glencora Borradaile, Amir Nayyeri and Farzad Zafarani
\n* ESA 2015
\n[ arXiv<\/a> ]<\/p>\n

Improving robustness of next-hop routing
\n<\/strong>Glencora Borradaile, W. Sean Kennedy, Gordon Wilfong and Lisa Zhang
\n* Journal of Combinatorial Optimization, pp. 1-15, doi\u00a010.1007\/s10878-014-9818-x December 2014.
\n[ arXiv<\/a> ]<\/p>\n

Planar induced subgraphs of sparse graphs<\/strong>
\nGlencora Borradaile, David Eppstein and Pingan Zhu
\n* Journal of Graph Algorithms and Applications, Vol. 19, no. 1, pp. 281-297, 2015.
\n* Graph Drawing 2014
\n[ arXiv<\/a> ]<\/p>\n

Covering nearly surface-embedded graphs with a fixed number of balls<\/strong>
\nGlencora Borradaile and Erin Wolf Chambers
\n* Discrete & Computational Geometry, pp. 979-996, volume 54, issue 4, 2014.
\n[ arXiv<\/a> ]<\/p>\n

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

Algorithms for Optimization Problems in Planar Graphs
\n<\/strong>Glencora Borradaile, Philp Klein, D\u00e1niel Marx, and Claire Mathieu.
\n* Dagstuhl Reports, pp. 35\u201357, volume 3, number 10, 2014.
\n[ doi<\/a> ]<\/p>\n

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

Maximum st-flow in directed planar graphs via shortest paths.
\n<\/strong>Glencora Borradaile and Anna Harutyunyan.
\n* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
\n[ arXiv<\/a> ]<\/p>\n

Boundary-to-boundary flows in planar graphs.<\/strong>
\nGlencora Borradaile and Anna Harutyunyan.
\n* International Workshop on Combinatorial Algorithms (IWOCA) 2013.
\n[ arXiv<\/a> ]<\/p>\n

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

Connectivity oracles for planar graphs
\n<\/strong>Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen.
\n* Scandinavian Symposium and Workshops on Algorithm Theory\u00a0(SWAT), 2012.
\n[\u00a0arXiv<\/a> ]<\/p>\n

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

Batch active learning via coordinating \u00a0matching
\n<\/strong>Javad Azimi, Alan Fern, Xiaoli Fern, Glencora Borradaile, and Brent Heeringa.
\n* International Conference on Machine Learning (ICML), 2012.
\n[ arXiv<\/a> ]<\/p>\n

Approximation algorithms for constrained knapsack problems
\n<\/strong>Glencora Borradaile, Brent Heeringa and Gordon Wilfong.
\n* Journal of Discrete Algorithms special issue for IWOCA 2011, 2012.
\n* International Workshop on Combinatorial Algorithms (IWOCA), 2011.
\n[\u00a0arXiv<\/a> ]<\/p>\n

Polynomial-time approximation schemes for connectivity problems in bounded-genus graphs.<\/strong>
\nGlencora Borradaile, Erik Demaine and Siamak Tazari.
\n* Algorithmica, 2012.
\n* Int\u2019l Symp. on Theoretical Aspects of Computer Science (STACS), 2009.
\n[ arXiv<\/a> ]<\/p>\n

Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time<\/strong>
\nGlencora Borradaile, Philip Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen.
\n* To appear: SIAM Journal on Computing.
\n* Foundations of Computer Science (FOCS), 2011.
\n[ arXiv<\/a> ]<\/p>\n

Multiple source, single sink maximum flow in a planar graph<\/strong>
\nGlencora Borradaile and Christian Wulff-Nilsen.
\n* Manuscript, 2010.
\n[ arXiv<\/a> ]<\/p>\n

Randomly removing g handles at once.<\/strong>
\nGlencora Borradaile, James Lee and Anastasios Sidiropoulos.
\n* Computational Geometry: Theory and Applications special issue for SoCG 2009, volume 43, 2010.
\n* Symposium on Computational Geometry (SoCG), 2009.
\n[ arXiv<\/a> ]<\/p>\n

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

An O(n log n) algorithm for maximum st-flow in a directed planar graph. <\/strong>
\nGlencora Borradaile and Philip Klein.
\n* Journal of the ACM, 56(2), 2009.
\n* Symposium on Discrete Algorithms (SODA), 2006.
\n[ pdf, full version<\/a> ]<\/p>\n

Planarity Testing
\n<\/strong>* Entry in the Encyclopedia of Algorithms, edited by Ming-Yang Kao. 2008.
\n[\u00a0pdf<\/a> ]<\/p>\n

Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon. <\/strong>
\nGlencora Borradaile, Philip Klein and Claire Mathieu.
\n* Workshop of Algorithms and Data Structures (WADS), 2007.
\n[ incorporated into journal version listed above ]<\/p>\n

Safe and tight linear estimators for global optimization.<\/strong>
\nGlencora Borradaile and Pascal Van Hentenryck.
\n* Mathematical Programming, 102(3), 2005.
\n[ pdf<\/a> ]<\/p>\n

Exploiting Planarity for Network Flow and Connectivity Problems
\n<\/strong>Glencora Borradaile.
\n<\/strong>Dissertation, Brown University, December 2007.
\n[ pdf<\/a> ]
\n<\/a><\/p>\n

Publications by my students during their studies and funded by my research grants<\/h3>\n

A PTAS for subset TSP in minor-free graphs.<\/strong>
\nHung Le.
\nSODA, 2020.
\n[ arXiv<\/a> ]<\/p>\n

Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs.<\/strong>
\nHung Le and Baigong Zheng.
\nCOCOON, 2019.
\n[ arVix<\/a> ]<\/p>\n

A better bound on the largest induced forests in triangle-free planar graphs.<\/strong>
\nHung Le.
\nGraphs and Combinatorics, 34(6), 2018.
\n[ arXiv<\/a> ]<\/p>\n","protected":false},"excerpt":{"rendered":"

Publications by my students while they were studying with me that I did not co-author are below. Defend Dissent: Digital Suppression and Cryptographic Defense of Social Movements Glencora Borradaile * Open Textbook @ OSU, 2021 The Motivated Can Encrypt (Even with PGP) Glencora Borradaile, Kelsy Kretschmer, Michele Gretes, Alexandria LeClerc * PETS 2021 [ arXiv […]<\/p>\n","protected":false},"author":3747,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"open","template":"","meta":{"footnotes":""},"class_list":["post-780","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/pages\/780","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=780"}],"version-history":[{"count":94,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/pages\/780\/revisions"}],"predecessor-version":[{"id":1404,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/pages\/780\/revisions\/1404"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}