The World is Flat: Algorithms for Classical Optimization Problems Restricted to Planar Graphs
March 28, 2012
ABSTRACT:
Maximum flow, shortest paths, traveling salesman, Steiner tree, multiterminal cut---for such well-studied graph problems, one might think nothing new can be said. However, when the input is restricted to planar graphs, new techniques become applicable, leading to nearly linear-time exact algorithms for some of the problems and nearly linear-time approximation schemes for others. The talk will survey some of the recent developments on these problems and indicate some of the techniques involved.
Maximum flow, shortest paths, traveling salesman, Steiner tree, multiterminal cut---for such well-studied graph problems, one might think nothing new can be said. However, when the input is restricted to planar graphs, new techniques become applicable, leading to nearly linear-time exact algorithms for some of the problems and nearly linear-time approximation schemes for others. The talk will survey some of the recent developments on these problems and indicate some of the techniques involved.