An O(n * log(n)) algorithm for maximum st-flow in a directed planar graph (Borradaile, Klein)

Asked Mar 27 '19 at 20:27

Active Mar 27 '19 at 20:27

Viewed 81 times

Could someone explain to me using an example how Borradaile-Klein's algorithm for maximum flow works? http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6392&rep=rep1&type=pdf

There are a lot of Ford-Fulkerson's examples (https://www.youtube.com/watch?v=Tl90tNtKvxs) but I didn't find an example for Borradaile-Klein algorithm.

Thank you.

asked Mar 27 '19 at 20:27

Pawel_DM

Klein and Shay Mozes have some lecture notes (http://courses.csail.mit.edu/6.889/fall11/lectures/) and a book (http://www.planarity.org/) that cover this algorithm. I can answer specific questions about this algorithm (I was Klein's PhD student) but I don't have the energy to write new tutorial material about it. – David Eisenstat Mar 28 '19 at 12:00

0 Answers0