Finding all min st-cuts in planar graphs

In 1961, Gomory and Hu observed that the minimum st-cuts in an edge-weighted, undirected graph, for all pairs of vertices, can be represented compactly by a tree: the GH-tree. Not only that, they showed that one can find this tree with only n-1 minimum cut computations. Besides improvements to max flow/min cut algorithms, not much progress has been made on the all-pairs min-cut problem: Gusfield (’90) simplified Gomory and Hu’s algorithm (without improvements the asymptotic running time) and Balghat et. al. (’07) showed how to find a GH-tree for unweighted graphs in time faster than required for n-1 min cut computations.

Here we study the problem in planar graphs. Using the duality of cuts and cycles and small, balanced separators, we show how to find a GH-tree for weighted, undirected planar graphs in O(n polylog n) time.

To appear in FOCS’10. Joint work with Piotr Sankowski and Christian Wulff-Nilsen

Speaker Details

Glencora Borradaile is an Assistant Professor in the School of Electrical Engineering and Computer Science at Oregon State University. She studied applied math at the University of Western Ontario (B.Sc. 2002), computer science at Brown University (Ph.D. 2008) and held an NSERC postdoctoral fellowship in the department of Combinatorics and Optimization at the University of Waterloo. More details can be found at www.glencora.org

Date:
Speakers:
Glencora Borradaile
Affiliation:
Oregon State University

    • Portrait of Jeff Running

      Jeff Running