Friday, November 2nd, 2012 4:15pm-5:00pm Burnside 1214
Mathematical Optimization, Office of Naval Research
Dualizing Dijkstra's Algorithm for the Min-Cut Problem

Suppose we want to find a minimum-capacity (s,t)-cut in a graph. Then, of course, we can use any maximum-flow algorithm to compute a minimum (s,t)-cut. If the graph happens to be planar, then an alternative approach would be to first find the dual graph, and then find a shortest (s,t)-path using, say, Dijkstra's algorithm. If the graph is not planar, this alternative approach would appear to break down. In fact, we show that is not the case. In particular, an appropriate dual version of Dijkstra's algorithm can solve the minimum (s,t)-cut problem in class of graphs that includes and goes well beyond the class of planar graphs.

Fall 2012 Schedule