• Calendar

February 1, Tuesday
12:00 – 13:30

We consider the problem of finding a maximum flow in directed planar graphs with multiple sources and sinks. For general (i.e., non-planar) graphs, the multiple-source multiple-sink maximum flow problem is as difficult as the standard single-source single-sink one. The reduction, however, does not preserve planarity. No efficient planarity exploiting algorithms for this problem were known until the current line of work. We present a divide-and-conquer algorithm that solves the problem on a planar graph with n nodes in O(n^1.5 log(n)) time. This is asymptotically faster than any previously known algorithm. Joint work with Glencora Borradaile, Philip Klein, Yahav Nussbaum and Christian Wulff-Nilsen. Preprints can be found at http://arxiv.org/abs/1012.5870 and http://arxiv.org/abs/1008.5332