8 citations · 31 across the 9 of their papers we have counts for
8 papers · 1 filter
Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities
Julian Enoch, Kyle Fox, Dor Mesica +1
We give an -time algorithm for computing maximum integer flows in planar graphs with integer arc {\em and vertex} capacities bounded by…
Minimum Cuts in Surface Graphs
Erin W. Chambers, Jeff Erickson, Kyle Fox +1
We describe algorithms to efficiently compute minimum -cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph with $…
Faster Algorithms for the Geometric Transportation Problem
Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi +2
Let and be two point sets in , with and where is a constant. Next, let such that $\sum_{r \in R } λ(r) = \sum_…
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren
Let be an edge-weighted directed graph with vertices embedded on an orientable surface of genus . We describe a simple deterministic lexicographic perturbation scheme th…
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…
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox, Philip N. Klein, Shay Mozes
Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge…