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],
  • 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.
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],
  • 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.
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],
- almost linear time algorithm for all-source all-sink max-fl

[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.

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],
- 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-low 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.

cat row 1, celldf adsf sad fdsa fsda fsdf sadad sda dsa ds 2
cat row 1, celldf adsf sad fdsa fsda fsdf sadad sda dsa ds 2
cat row 1, celldf adsf sad fdsa fsda fsdf sadad sda dsa ds 2

According to the report by Foundation for Polish Science working in Poland can be seen as hurting your scientific carrier (114873,10657310, Badacze_o_Polsce__praca_tam_moze_zaszkodzic_karierze.html">article in polish).

cat

We do not really agree with it and the above meme was meant to be self-ironic. It of course could be better - as everywhere. Anyway, if you would like to see how it is to work in Poland we have two postdoc positions in algorithms open - see the call.
According to the report by Foundation for Polish Science working in Poland can be seen as hurting your scientific carrier (114873, 10657310,Badacze_o_Polsce__praca_tam_moze_zaszkodzic_karierze.html">article in polish).

cat

We do not really agree with it and the above meme was meant to be self-ironic. It of course could be better - as everywhere. Anyway, if you would like to see how it is to work in Poland we have two postdoc positions in algorithms open - see the call.
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],
  • 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.

2 thoughts on “Presentation: Monge Property and Max-Flows in Planar Graphs

Leave a Reply

Your email address will not be published. Required fields are marked *