Arrow Research search

Author name cluster

Glencora Borradaile

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
1 author row

Possible papers

8

SODA Conference 2019 Conference Paper

Greedy spanners are optimal in doubling metrics

  • Glencora Borradaile
  • Hung Le 0001
  • Christian Wulff-Nilsen

We show that the greedy spanner algorithm constructs a (1 + ∊ )-spanner of weight ∊ − O ( d ) w (MST) for a point set in metrics of doubling dimension d, resolving an open problem posed by Gottlieb [10]. Our result generalizes the result by Narasimhan and Smid [13] who showed that a point set in d -dimension Euclidean space has a (1 + ∊ )-spanner of weight at most ∊ − O ( d ) w (MST). Our proof only uses the packing property of doubling metrics and greatly simplifies the proof of the same result in Euclidean space.

Details

FOCS Conference 2017 Conference Paper

Minor-Free Graphs Have Light Spanners

  • Glencora Borradaile
  • Hung Le 0001
  • Christian Wulff-Nilsen

We show that every H-minor-free graph has a light (1+≥ilon)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung \cite{GH12}. Our lightness bound is \[O\left(\frac{\sigma_H}{≥ilon^3}\log \frac{1}{≥ilon}\right)\] where \sigma_H = |V(H)|√{\log |V(H)|} is the sparsity coefficient of H-minor-free graphs. That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is 2^{O_H\left(\frac{1}{≥ilon^4}\log \frac{1}{≥ilon}\right)}n^{O(1)} where O_H ignores dependencies on the size of H. Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs[6].

Details

FOCS Conference 2011 Conference Paper

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

  • Glencora Borradaile
  • Philip N. Klein
  • Shay Mozes
  • Yahav Nussbaum
  • Christian Wulff-Nilsen

We give an O(n log 3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

Details

FOCS Conference 2010 Conference Paper

Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

  • Glencora Borradaile
  • Piotr Sankowski
  • Christian Wulff-Nilsen

For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log 5 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Our oracle can be extended to report the min st-cuts in time proportional to their size. Since all-pairs min si-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log 5 n) time and O(n log n) space and an explicit representation with additional O(C) time and space where G is the size of the basis. To obtain our results, we require that shortest paths be unique; this assumption can be removed deterministically with an additional O(log 2 n) running-time factor.

Details

FOCS Conference 2008 Conference Paper

A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

  • Glencora Borradaile
  • Philip N. Klein
  • Claire Mathieu

We give a randomized O(n 2 log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.

Details
v2026.09.13