Workshop on Kernelization 2013

Last week we organized Workshop on Kernelization (WorKer 2013) in Warsaw. The programmee included

  • an update meeting on graph cut problems,
  • two tutorials (Matroid theory and kernelization by Saket Saurabh, Stefan Kratsch and Magnus Wahlström and Kernel-size lower bounds: the evidence from complexity theory by Andrew Drucker),
  • two invited talks on techniques used outside the kernelization area which might turn out useful in kernelization (on planar graphs by Piotr Sankowski and on spanners by Seth Pettie)
  • a few short contributed talks

We hope it was fun! Below you can see some pictures.

 

 

Presentation: Monge Property and Max-Flows in Planar Graphs

If you are interested in max-flow computations in planar graphs, below is the talk I have given at WORKER 2013. It gives an overview of how to use shortest paths and Monge property to get the following three results:

  • O(n log log n) time algorithm for undirected max-flow in planar graphs [1], shop
  • almost linear time algorithm for all-source all-sink max-flow in undirected planar graphs, i.e., it computes Gumory-Hu tree [2],
  • almost linear time algorithm for single-source all-sink max-flow in directed planar graphs [3].

[1] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Improved algorithms for min cut and max flow in undirected planar graphs. STOC 2011: 313-322.
[2] Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen: Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. FOCS 2010: 601-610.
[3] Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen: Single Source - All Sinks Max Flows in Planar Digraphs. FOCS 2012: 599-608.