25 citations · 78 across the 26 of their papers we have counts for
33 papers
The Motivated Can Encrypt (Even with PGP)
Glencora Borradaile, Kelsy Kretschmer, Michele Gretes +1
Existing end-to-end-encrypted (E2EE) email systems, mainly PGP, have long been evaluated in controlled lab settings. While these studies have exposed usability obstacles for the av…
Low-stretch spanning trees of graphs with bounded width
Glencora Borradaile, Erin Wolf Chambers, David Eppstein +2
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph with a linear arrange…
Minimum bounded chains and minimum homologous chains in embedded simplicial complexes
Glencora Borradaile, William Maxwell, Amir Nayyeri
We study two optimization problems on simplicial complexes with homology over , the minimum bounded chain problem: given a -dimensional complex embed…
Whose Tweets are Surveilled for the Police: An Audit of Social-Media Monitoring Tool via Log Files
Glencora Borradaile, Brett Burkhardt, Alexandria LeClerc
Social media monitoring by law enforcement is becoming commonplace, but little is known about what software packages for it do. Through public records requests, we obtained log fil…
Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs
Glencora Borradaile, Hung Le, Baigong Zheng
We present two algorithms for the minimum feedback vertex set problem in planar graphs: an PTAS using a linear kernel and balanced separator, and a heuristic algorith…
Greedy spanners are optimal in doubling metrics
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
We show that the greedy spanner algorithm constructs a -spanner of weight for a point set in metrics of doubling dimension , resolving an open…
Minor-free graphs have light spanners
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
We show that every -minor-free graph has a light -spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung. Our lightness bou…
Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
Glencora Borradaile, Hung Le, Melissa Sherman-Bennett
Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has a…
Time-dependent shortest paths in bounded treewidth graphs
Glencora Borradaile, Morgan Shirley
We present a proof that the number of breakpoints in the arrival function between two terminals in graphs of treewidth is when the edge arrival functions are…
Light spanners for bounded treewidth graphs imply light spanners for -minor-free graphs
Glencora Borradaile, Hung Le
Grigni and Hung~\cite{GH12} conjectured that H-minor-free graphs have -spanners that are light, that is, of weight times the weight of the minimum spanning tree f…
Embedded-width: A variant of treewidth for plane graphs
Glencora Borradaile, Jeff Erickson, Hung Le +1
We define a special case of tree decompositions for planar graphs that respect a given embedding of the graph. We study the analogous width of the resulting decomposition we call t…
A PTAS for Three-Edge Connectivity in Planar Graphs
Glencora Borradaile, Baigong Zheng
We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement for every verte…
Minimum cycle and homology bases of surface embedded graphs
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox +1
We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of…
Towards single face shortest vertex-disjoint paths in undirected planar graphs
Glencora Borradaile, Amir Nayyeri, Farzad Zafarani
Given pairs of terminals in a graph , the min-sum vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ld…
Optimal dynamic program for r-domination problems over tree decompositions
Glencora Borradaile, Hung Le
There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems are optimal under the Strong E…
Improving Robustness of Next-Hop Routing
Glencora Borradaile, W. Sean Kennedy, Gordon Wilfong +1
A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop a…
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
Glencora Borradaile, David Eppstein, Amir Nayyeri +1
For an undirected -vertex graph with non-negative edge-weights, we consider the following type of query: given two vertices and in , what is the weight of a minim…
Density decompositions of networks
Glencora Borradaile, Theresa Migler, Gordon Wilfong
We introduce a new topological descriptor of a network called the density decomposition which is a partition of the nodes of a network into regions of uniform density. The decompos…
Covering nearly surface-embedded graphs with a fixed number of balls
Glencora Borradaile, Erin Wolf Chambers
A recent result of Chepoi, Estellon and Vaxes [DCG '07] states that any planar graph of diameter at most 2R can be covered by a constant number of balls of size R; put another way,…
Boundary-to-boundary flows in planar graphs
Glencora Borradaile, Anna Harutyunyan
We give an iterative algorithm for finding the maximum flow between a set of sources and sinks that lie on the boundary of a planar graph. Our algorithm uses only O(n) queries to s…
Maximum st-flow in directed planar graphs via shortest paths
Glencora Borradaile, Anna Harutyunyan
Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to short…
A polynomial-time approximation scheme for Euclidean Steiner forest
Glencora Borradaile, Philip Klein, Claire Mathieu
We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed eps > 0 and given n terminals in the plane with…
The two-edge connectivity survivable-network design problem in planar graphs
Glencora Borradaile, Philip Klein
Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every p…
Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler +3
Given an undirected graph, one can assign directions to each of the edges of the graph, thus orienting the graph. To be as egalitarian as possible, one may wish to find an orientat…