I've posted a whole bunch of notes on matchings on the course webpage.
Also, if you're interested in blocking flows and would like some more details (or if you just got lost in the discussion today (sorry!)), have a look at Chapter 18 of Dexter Kozen's book (Google book version here). It describes Dinic's algorithm that uses blocking flows, and also gives a faster O(n^3) time version. Using the dynamic trees that Danny will talk about on Wednesday, one can greatly speed up blocking-flow computations, as well as implementations of push-relabel.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment