Home

Glencora Borradaile

  1. Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.

    Fri, 04/09/2010 - 15:02 — SomNambul
    Authors: Glencora Borradaile, Christian Wulff-Nilsen, Piotr Sankowski
    Subjects: Discrete Mathematics
    Abstract

    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^5n)$ preprocessing time and $O(n\log n)$ space.
    We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly.
    Previously, no subquadratic time algorithm was known for this problem.

  2. Randomly removing g handles at once.

    Tue, 03/09/2010 - 16:01 — SomNambul
    Authors: James R. Lee, Glencora Borradaile, Anastasios Sidiropoulos
    Subjects: Computational Geometry
    Abstract

    Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$
    can be probabilistically embedded into a graph of genus $g-1$ with constant
    distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere
    with $g$ handles attached, Indyk and Sidiropoulos' method gives an embedding
    into a distribution over planar graphs with distortion $2^{O(g)}$, by
    iteratively removing the handles. By removing all $g$ handles at once, we
    present a probabilistic embedding with distortion $O(g^2)$ for both orientable
    and non-orientable graphs.

  3. Approximation Algorithms for Constrained Knapsack Problems.

    Tue, 10/06/2009 - 17:01 — SomNambul
    Authors: Glencora Borradaile, Brent Heeringa, Gordon Wilfong
    Subjects: Data Structures and Algorithms
    Abstract

    We study constrained versions of the knapsack problem in which dependencies
    between items are given by a graph. In one version, an item can be selected
    only if one of its neighbours is also selected. In the other version, an item
    can be selected only when all its neighbours are also selected. These problems
    generalize and unify several problems including the prize collecting and
    budgeted maximum coverage problems.

Math-arch

Syndicate content