Finding all min st-cuts in planar graphs

Speaker  Glencora Borradaile

Host  Nikhil Devanur Rangarajan

Affiliation  Oregon State University

Duration  01:00:26

Date recorded  17 August 2010

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

©2010 Microsoft Corporation. All rights reserved.
> Finding all min st-cuts in planar graphs